Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height =[2,1,5,6,2,3],return 10. 辅助栈：方法1（扫描3遍）
1 class Solution { 2 public: 3 int largestRectangleArea(vector &height) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 vector area(height.size()); 7 8 stack s; 9 for(int i = 0; i < height.size(); i++)10 if (s.empty())11 {12 s.push(i);13 area[i] = 0;14 }15 else16 {17 while(!s.empty())18 {19 if (height[i] <= height[s.top()])20 {21 s.pop();22 }23 else24 break;25 }26 27 if (s.empty())28 area[i] = i;29 else30 area[i] = i - s.top() - 1;31 s.push(i); 32 }33 34 while(!s.empty())35 s.pop();36 37 for(int i = height.size() - 1; i >= 0; i--)38 if (s.empty())39 {40 s.push(i);41 area[i] += 0;42 }43 else44 {45 while(!s.empty())46 {47 if (height[i] <= height[s.top()])48 {49 s.pop();50 }51 else52 break;53 }54 55 if (s.empty())56 area[i] += height.size() - i - 1;57 else58 area[i] += s.top() - i - 1;59 s.push(i);60 }61 62 int maxArea = 0;63 for(int i = 0; i < area.size(); i++)64 {65 maxArea = max(maxArea, height[i] * (area[i] + 1));66 }67 68 return maxArea;69 }70 };
辅助栈：方法3
1 class Solution { 2 public: 3 int largestRectangleArea(vector &height) { 4 // Start typing your C/C++ solution below 5 // DO NOT write int main() function 6 int maxArea = 0; 7 stack s; 8 9 for(int i = 0; i < height.size(); i++)10 if (s.empty())11 {12 s.push(i);13 }14 else15 {16 while(!s.empty())17 {18 if (height[s.top()] <= height[i])19 {20 s.push(i);21 break;22 }23 else24 {25 int index = s.top();26 s.pop();27 int leftWidth = s.empty() ? index : index - s.top() - 1;28 int rightWidth = i - index - 1;29 maxArea = max(maxArea, height[index] * (leftWidth + rightWidth + 1));30 }31 }32 33 if (s.empty())34 s.push(i);35 }36 37 int rightIndex = s.empty() ? 0 : s.top() + 1;38 39 while(!s.empty())40 {41 int index = s.top();42 s.pop();43 int leftWidth = s.empty() ? index : index - s.top() - 1;44 int rightWidth = rightIndex - index - 1;45 maxArea = max(maxArea, height[index] * (leftWidth + rightWidth + 1));46 }47 48 49 return maxArea;50 }51 };
用辅助栈：方法2（扫描一遍）
1 struct Node 2 { 3 int val; 4 int index; 5 int area; 6 Node(){} 7 Node(int v, int idx):val(v), index(idx){} 8 }; 9 10 class Solution {11 public:12 int largestRectangleArea(vector &height) {13 // Start typing your C/C++ solution below14 // DO NOT write int main() function15 stack s;16 int maxArea = 0;17 for(int i = 0; i < height.size(); i++)18 if (s.empty())19 s.push(Node(height[i], i));20 else21 {22 while(!s.empty())23 {24 Node node = s.top();25 if (node.val <= height[i])26 {27 s.push(Node(height[i], i));28 break;29 }30 else31 {32 s.pop();33 int leftIndex = s.empty() ? 0 : s.top().index + 1; 34 maxArea = max(maxArea, (i - node.index + node.index - leftIndex) * node.val); 35 }36 }37 38 if (s.empty())39 s.push(Node(height[i], i));40 }41 42 int index = height.size();43 while(!s.empty())44 {45 Node node = s.top();46 s.pop();47 int leftIndex = s.empty() ? 0 : s.top().index + 1;48 maxArea = max(maxArea, (index - node.index + node.index - leftIndex) * node.val);49 }50 51 return maxArea;52 }53 };