C++ O(N^2) implementation using subroutine from question 84. Largest Rectangle in Histogram


  • 0
    N
    int maximalRectangle(vector<vector<char>>& matrix) {
            int ans = 0;
            vector<int> buf;
            for (int i = 0; i < matrix.size(); i++) {
                if (i == 0) {
                    for (int j = 0; j < matrix[0].size(); j++) {
                        buf.push_back(matrix[0][j] - '0');
                    }
                } else {
                    for (int j = 0; j < matrix[0].size(); j++) {
                        int cur = matrix[i][j] - '0';
                        if (cur == 1) {
                            buf[j] = buf[j] + 1;
                        } else {
                            buf[j] = 0;
                        }
                    }
                }
                
                int temp = largestRectangleArea(buf);
                if (temp > ans) {
                    ans = temp;
                }
            }
            return ans;
        }
        
       
        
            
       int largestRectangleArea(vector<int>& height) {
                stack<int> s;
                vector<int> _height = height;
                _height.push_back(0);
                int ans = 0;
                for (int i = 0; i < _height.size(); i++) {
                    if (s.empty()) {
                        s.push(i);
                    } else {
                        int top = s.top();
                        if (_height[top] > _height[i]) {
                            
                           while (!s.empty() && _height[top] > _height[i]) {
                                    s.pop();
                                    if (s.empty()) {
                                        int curr = _height[top] * i;
                                        if (curr > ans) {
                                            ans = curr;
                                        }
                                    } else {
                                        int curr = _height[top] * (i - s.top() - 1);
                                        if (curr > ans) {
                                            ans = curr;
                                        }
                                        
                                        top = s.top(); 
                                    }
                            }
                          s.push(i);
                        } else {
                            s.push(i);
                        }
                    }
                }
                return ans;
            }

Log in to reply
 

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