Leetcode 84. Largest Rectangle in Histogram | | Leetcode 84. Largest Rectangle in Histogram 文章作者:Tyan博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution O(N^2) 12345678910111213141516171819202122232425class Solution {public: int largestRectangleArea(vector<int>& heights) { int maxArea = 0; for(int i = 0; i < heights.size(); i++) { int left = i; int right = i; for(left = i; left >= 0; left--) { if(heights[left] < heights[i]) { break; } } for(right = i; right < heights.size(); right++) { if(heights[right] < heights[i]) { break; } } int area = (right - 1 - left - 1 + 1) * heights[i]; if(area > maxArea) { maxArea = area; } } return maxArea; }}; O(N) 1234567891011121314151617181920212223class Solution {public: int largestRectangleArea(vector<int>& heights) { int maxArea = 0; stack<int> border; heights.push_back(0); for(int i = 0; i < heights.size(); i++) { if(border.empty() || heights[i] > heights[border.top()]) { border.push(i); } else { int index = border.top(); border.pop(); int area = heights[index] * (border.empty()?i:i - border.top() - 1); if(area > maxArea) { maxArea = area; } i--; } } return maxArea; }}; Reference https://leetcode.com/problems/largest-rectangle-in-histogram/description/ 如果有收获,可以请我喝杯咖啡! 赏 微信打赏 支付宝打赏