My 16ms C++ O(n) code without a stack
Basically, I find the range (left[i], right[i]) within which the height of every element is at least height[i]. For each i, there is a rectangular with area hei
Basically, I find the range (left[i], right[i]) within which the height of every element is at least height[i]. For each i, there is a rectangular with area height[i] * (right[i]-left[i]+1), and the largest area must be one of them. Then run all i to find the largest area. Please notice it takes O(n) time to fill left[i] and right[i] if we use DP. We can use amortization analysis to find this out. If you think about the worst case for a certain i, if it takes k steps in the while loop to get left[i]. Then it means there are k indices (for each j update below) which only take 1 step each in the loop to find left item for these indices. Then the average number of steps of these k+1 indices is const. So it takes O(n) to fill left and right arrays.\n\n    class Solution {\n    public:\n        int largestRectangleArea(vector<int>& height) {\n            int N=height.size(), i, j, l, r, area=0, temp;\n            if(N==0) return 0;\n            vector<int> left(N), right(N);\n            left[0]=0;  //fill left[i] in the for loop\n            for(i=1; i<N; ++i){\n                l=i;\n                j=i-1;\n                while(j>=0&&height[j]>=height[i]){   // amortization shows const steps for this loop\n                    if(height[j]==height[i]){\n                        l=left[j];\n                        break;\n                    }\n                    l=left[j];\n                    j=left[j]-1;\n                }\n                left[i]=l;\n            }\n            right[N-1]=N-1;  //fill right[i] in the for loop\n            for(i=N-2; i>=0; --i){\n                r=i;\n                j=i+1;\n                while(j<N && height[j]>=height[i]){ \n                    if(height[j]==height[i]){\n                        r=right[j];\n                        break;\n                    }\n                    r=right[j];\n                    j=right[j]+1;\n                }\n                right[i]=r;\n            }\n            for(i=0; i<N; ++i){\n                temp=height[i]*(right[i]-left[i]+1);\n                if(temp>area) area = temp;\n            }\n            return area;\n        }\n    };
['Dynamic Programming', 'C++']