HELP... Different results between run code and submit.


  • 0
    X

    Different results between run code and submit. I don't understand why the run code button and submit button give me different results. The code seems work for me by hand simulating. I appreciate any help to indicate the problem.

    class Solution {
    public:
        int largestRectangleArea(vector<int>& height) {
            vector<int> index;
            int res = 0;
            for(int i = 0 ; i <= height.size() ; i++){
                if(index.empty() || height[index.back()] <= height[i] ){
                    index.push_back(i);
                }
                else{
                    while(!index.empty() && height[index.back()] > height[i]){
                        //if current number is smaller, calculate the biggest area so far
                        int h = height[index.back()];
                        index.pop_back();
                        int leftindex = index.empty() ? -1 : index.back();
                        //between leftindx and i is larger than h
                        res = max(res, h*(i - leftindex-1));
                    }
                    index.push_back(i);
                }
            }
            return res;
            
        }
    };

  • 0
    D

    The problem lies here:

    for(int i = 0 ; i <= height.size() ; i++){
        if(index.empty() || height[index.back()] <= height[i] ){
             ....
    

    when i equals to height.size(), accessing height[i] causes array index out-of-bound. That's why you have different results for "submit" and "run code".

    First you need to use i < height.size() in the for loop. You can also append a '0' at the end of height, so you don't need to worry about if anything is left in the stack.

    The following code got AC

    class Solution {
    public:
        int largestRectangleArea(vector<int>& height) {
            vector<int> index;
            int res = 0;
            height.push_back(0);  // guard
            for(int i = 0 ; i < height.size() ; i++){
                if(index.empty() || height[index.back()] <= height[i] ){
                    index.push_back(i);
                }
                else{
                    while(!index.empty() && height[index.back()] > height[i]){
                        //if current number is smaller, calculate the biggest area so far
                        int h = height[index.back()];
                        index.pop_back();
                        int leftindex = index.empty() ? -1 : index.back();
                        //between leftindx and i is larger than h
                        res = max(res, h*(i - leftindex-1));
                    }
                    index.push_back(i);
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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