Seeking for help understand intuition behind Leetcode 84. Largest Rectangle in Histogram. Problem description: Given an array heights where each element represents the height of a bar in a histogram, find the area of the largest rectangle that can be formed within the histogram. Examples Input: [2,1,5,6,2,3] Output: 10 Explanation: The largest rectangle (area = 10) is formed by bars [5, 6] (width = 2, height = 5). I can't figure out how to approach the optimal solution, in other words, what should be the objective that I should be looking for? due to unawareness of which, the best I can do is to use decision tree with brute force to check for each index, whether or not the bar at the index is included in the largest rectangle, naturally, it gives me time limit exceeded: class Solution: def largestRectangleArea(self, heights: List[int]) -> int: ans = 0 def myFunc( idx, myMin, length, heights ): nonlocal ans endsHere = myMin * length ans = max( endsHere, ans ) if idx < len( heights ): if heights[idx] > myMin: myFunc( idx + 1, heights[idx], 1, heights ) myFunc( idx + 1, min( heights[idx], myMin ), length + 1, heights ) myFunc( 0, float('inf'), 0, heights ) return ans I then managed to find the optimal solution online: class Solution { public: int largestRectangleArea(vector<int>& heights) { int ans = 0; stack<int> stack; for (int i = 0; i <= heights.size(); ++i) { while (!stack.empty() && (i == heights.size() || heights[stack.top()] > heights)) { const int h = heights[stack.top()]; stack.pop(); const int w = stack.empty() ? i : i - stack.top() - 1; ans = max(ans, h * w); } stack.push(i); } return ans; } }; Guess it is because of lack of that intuition, I don't understand its description: "For each index i, store the index of the first bar to the left and right, respectively, that is shorter than height." Why do I need the index of the first bar to the left and right that is shorter than height for each index? What does it serve? Continue reading...
