📊 Monotonique Stack Solution Intuition (Javascript)
Oh, hard problem it is, isn\'t it? \nLet\'s develop some intuition on how to access it.\n\n## Increasing \nWhen the heights are increasing, we can always build 
Oh, **hard problem** it is, isn\'t it? \nLet\'s develop some intuition on how to access it.\n\n## Increasing \nWhen the heights are **increasing**, we can always build rectangle from a point there a previous height started, to the current point. \n![image](https://assets.leetcode.com/users/images/5b931e15-5391-4cd5-bed3-a894533829e1_1630144379.5151935.jpeg)\nE.g we have heights [1, 2, 5]. In point 2 we can build rectangle of the height 1. In the point 5 we can build rectangle of height 2, starting from index 1, or height 1, starting from index 0. \n\nLet\'s put the height, and the index, from where it\'s possible to build rectangle of this height, into a stack. \n\t```javascript\n\tstack.push([index, height])\n\t```\n## Decreasing \nWhen the height is **decreasing**, we couldn\'t build rectangle of any previous height, heigher than the current one. So it\'s the place to make evaluation. \n![image](https://assets.leetcode.com/users/images/f6fbe0c0-d0b3-42ae-9965-9f6a351512b8_1630145345.9980621.jpeg)\n\n\nWe\'ll pop all the heights bigger than the current one from the stack, and estimate the rectangles which could be build to this point:\n```javascript\nwhile (stack.length && stack[stack.length - 1][1] > heights[i]) {\n                let [pos, height] = stack.pop();\n                res = Math.max(res, (i - pos) * height);\n\t}\n```\n## What to put in the stack?\nIt\'s seems like we put in the stack the current index we are processing? \nAlmost. \nBut when we pop up all the heights which are bigger than the current one, guess where current height could start? From any of this points. \nImagine we have array [1, 3, 5, 2]. At the height of 2 we pop up 5 and 3, but rectangle of the height 2 can start from index 1, not from index 3!\nSo, we put in the stack the **earliest point, from there this height could start**. Which is either current index, or the last height poped from the stack. \n## Append 0 to heights\nTo make sure we processed all the heights, we can add additinal while statement in the end, or do more elegant solution - append 0 to the end of heights.\n\n## Full code\n```javascript\nheights.push(0)  \nlet stack = [];\nlet res = 0;\nfor (let i = 0; i < heights.length; i++) {\n\tlet heightStart = i;\n\twhile (stack.length && stack[stack.length - 1][1] > heights[i]) {\n\t\t\tlet [pos, height] = stack.pop();\n\t\t\tres = Math.max(res, (i - pos) * height);\n\t\t\theightStart = pos; \n\t\t}\n\tstack.push([heightStart, heights[i]]);\n}\nreturn res;\n```\n\n\n
['Stack', 'JavaScript']