Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function largestRectAtRow(rowNum) {
- var area = [];
- var leftAdjCols = [];
- var rigthAdjCols = [];
- var i, t;
- var stack = [];
- for (i = 0; i < matrix.length; ++i) {
- while (stack.length != 0) {
- if (matrix[i][rowNum] <= matrix[stack[stack.length - 1]][rowNum]) {
- stack.pop();
- } else {
- break;
- }
- }
- if (stack.length == 0) {
- t = -1;
- } else {
- t = stack[stack.length - 1];
- }
- // (i - t - 1): number of adjacent columns to the left of i-th column
- var leftAdj = (i - t - 1);
- leftAdjCols[i] = leftAdj;
- var leftSum = 0;
- for (var c = i - leftAdj; c < leftAdj; ++c) {
- leftSum += columnsWidths[c];
- }
- area[i] = leftSum;
- stack.push(i);
- }
- while (stack.length != 0) {
- stack.pop();
- }
- for (i = matrix.length - 1; i >= 0; --i) {
- while (stack.length != 0) {
- if (matrix[i][rowNum] <= matrix[stack[stack.length - 1]][rowNum]) {
- stack.pop();
- } else {
- break;
- }
- }
- if (stack.length == 0) {
- t = matrix.length;
- } else {
- t = stack[stack.length - 1];
- }
- // (i - t - 1): number of adjacent columns to the right of i-th column
- var rigthAdj = t - i - 1;
- var rigthSum = 0;
- rigthAdjCols[i] = rigthAdj;
- for (c = i + 1; c <= i + rigthAdj; ++c) {
- rigthSum += columnsWidths[c];
- }
- area[i] += rigthSum;
- stack.push(i);
- }
- var maxRect = {left: 0, top: 0, width: 0, height: 0};
- for (i = 0; i < matrix.length; ++i) {
- var width = area[i] + columnsWidths[i];
- var height = matrix[i][rowNum];
- if (maxRect.width * maxRect.height < width * height) {
- var top = 0;
- for (c = 0; c <= rowNum; ++c) {
- top += rowHeights[c];
- }
- top -= matrix[i][rowNum];
- var left = 0;
- for (c = 0; c < i; ++c) {
- left += columnsWidths[c];
- }
- for (c = 0; c < leftAdjCols[i]; ++c) {
- left -= columnsWidths[i - 1 - c];
- }
- maxRect = { left: left, top: top, width: width, height: height };
- }
- }
- return maxRect;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement