Very simple solution yet accepted with 16ms in C++


  • 0

    Two major points explained here:

    • index_stack will only store the index of ascending heights if the coming height is not consistent with this feature, we have to pop out some of them till it does, while the popping process we calculate the area;
    • the final 0 pushed back to the heights at the very beginning is used to clear up the stack.
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            heights.push_back(0);
            int cur = 0, maxArea = 0, top = 0;
            int *stack = new int[heights.size()]();
            stack[top] = -1;
            for(int i = 0; i < heights.size(); ++i){
                while(top>0 && heights[stack[top]] >= heights[i]){
                    cur = (i-stack[top-1]-1)*heights[stack[top]];
                    top--;
                    maxArea = max(cur, maxArea);
                }
                stack[++top] = i;
            }
            delete [] stack;
            return maxArea;
        }
    };
    


  • 1
    L

    A -1 is put at the bottom, so it should be
    int index_stack[size + 1];
    if height is in ascending order


  • 0

    @L.K.Rebellion You are sharp on this, but do you notice there is a

    heights.push_back(0);

    before I retrieve the size?


  • 0
    W

    This code is non-standard C++ as it uses a variable-length array (VLA). I'm surprised that this is allowed on leetcode.
    VLAs are supported as language extension by several compilers and are faster to create than dynamic arrays. That's why your code is a few ms faster than those written in ISO C++.


  • 0

    @Walter11 said in Very simple solution yet accepted with 16ms in C++:

    That's why your code is a few ms faster than those written in ISO C++.

    Can you back that up?

    I just tried his original, got accepted in 16ms, 13ms, 16ms. Then I changed it to use new[] and delete[] and it got accepted in 13ms, 13ms, 19ms. Seems rather equivalent to me, as I had very much expected.


  • 0
    W

    @StefanPochmann This is just experience that calls to the heap allocator tend to be expensive. The compiler may optimise that away (if it can see that the memory is freed within the same function), i.e. avoid heap allocation. But I havn't tested this here. In any case, I still don't understand why this code was accepted -- it's not even C++.


  • 0

    @Walter11 Perhaps you could show me some more official documentation to present your ideas, which is quite refreshing and interesting. Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.