Advertisement
Guest User

Untitled

a guest
Nov 12th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. function largestRectAtRow(rowNum) {
  2.  
  3. var area = [];
  4. var leftAdjCols = [];
  5. var rigthAdjCols = [];
  6. var i, t;
  7. var stack = [];
  8.  
  9. for (i = 0; i < matrix.length; ++i) {
  10.  
  11. while (stack.length != 0) {
  12.  
  13. if (matrix[i][rowNum] <= matrix[stack[stack.length - 1]][rowNum]) {
  14. stack.pop();
  15. } else {
  16. break;
  17. }
  18. }
  19. if (stack.length == 0) {
  20. t = -1;
  21. } else {
  22. t = stack[stack.length - 1];
  23. }
  24.  
  25. // (i - t - 1): number of adjacent columns to the left of i-th column
  26. var leftAdj = (i - t - 1);
  27. leftAdjCols[i] = leftAdj;
  28.  
  29. var leftSum = 0;
  30. for (var c = i - leftAdj; c < leftAdj; ++c) {
  31. leftSum += columnsWidths[c];
  32. }
  33. area[i] = leftSum;
  34.  
  35. stack.push(i);
  36. }
  37.  
  38. while (stack.length != 0) {
  39. stack.pop();
  40. }
  41.  
  42. for (i = matrix.length - 1; i >= 0; --i) {
  43.  
  44. while (stack.length != 0) {
  45.  
  46. if (matrix[i][rowNum] <= matrix[stack[stack.length - 1]][rowNum]) {
  47. stack.pop();
  48. } else {
  49. break;
  50. }
  51. }
  52. if (stack.length == 0) {
  53. t = matrix.length;
  54. } else {
  55. t = stack[stack.length - 1];
  56. }
  57.  
  58. // (i - t - 1): number of adjacent columns to the right of i-th column
  59. var rigthAdj = t - i - 1;
  60. var rigthSum = 0;
  61. rigthAdjCols[i] = rigthAdj;
  62. for (c = i + 1; c <= i + rigthAdj; ++c) {
  63. rigthSum += columnsWidths[c];
  64. }
  65. area[i] += rigthSum;
  66.  
  67. stack.push(i);
  68. }
  69.  
  70. var maxRect = {left: 0, top: 0, width: 0, height: 0};
  71. for (i = 0; i < matrix.length; ++i) {
  72.  
  73. var width = area[i] + columnsWidths[i];
  74. var height = matrix[i][rowNum];
  75.  
  76. if (maxRect.width * maxRect.height < width * height) {
  77.  
  78. var top = 0;
  79. for (c = 0; c <= rowNum; ++c) {
  80. top += rowHeights[c];
  81. }
  82. top -= matrix[i][rowNum];
  83.  
  84. var left = 0;
  85. for (c = 0; c < i; ++c) {
  86. left += columnsWidths[c];
  87. }
  88. for (c = 0; c < leftAdjCols[i]; ++c) {
  89. left -= columnsWidths[i - 1 - c];
  90. }
  91.  
  92. maxRect = { left: left, top: top, width: width, height: height };
  93. }
  94. }
  95.  
  96. return maxRect;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement