题目链接:
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
方法一：暴力法
柱子i和j范围内的最大矩形，我们可以遍历i至j去查找范围内最小的高度H，宽L为柱子i和j的距离。H*L就是柱子i和j范围内的最大矩形。
然后我们再遍历所有柱子的组合，最后在所有的情况中得到最大值。
1. class Solution { 2. public: 3. int largestRectangleArea(vector<int>& heights) { 4. int n = heights.size(); 5. if (n == 0) { 6. return 0; 7. } 8. 9. int max = 0; 10. for (int i = 0; i < n; ++i) { 11. int h = heights[i]; 12. for (int j = i; j < n; ++j) { 13. h = h < heights[j] ? h : heights[j]; 14. int L = j - i + 1; 15. if (h == 0) { 16. break; 17. } 18. max = max > h * L ? max : h * L; 19. } 20. } 21. return max; 22. } 23. };方法二：
我们可以分别求出包含每个柱子的最大矩形面积，然后选择最大的。
对于一个柱子求包含它的最大矩形，那么该柱子的高度必定等于矩形的高度。我们只要分别求出左右两边最近的高度小于当前柱子的下标，下标的距离即矩形的宽。当前柱子的高度即为矩形的高。
我们用leftMin[i]和rightMin[i]保存柱子i左右两边最近高度小于H的柱子下标。
特殊的，leftMin[0]=-1，rightMin[n-1] = n。
对于查找左边第一个小于柱子i的柱子下标，我们可以这样：
1.先判断是否大于左边相邻的柱子，是的话就将其下标记录至数组。
2.不是的话我们跳跃至leftMin[i-1]，判断leftMin[i-1]的柱子是否小于柱子i。
如果柱子i-1高于柱子i，因为leftMin[i-1]+1至i-1均大于柱子i-1，所以该范围内的柱子也高于柱子i。
3.循环上述步骤直至找到符合条件的柱子。
1. class Solution { 2. public: 3. int largestRectangleArea(vector<int>& heights) { 4. int n = heights.size(); 5. if (n == 0) { 6. return 0; 7. } 8. 9. // 保存左边小于当前高度的柱子下标 10. int leftMin[n] = {-1}; 11. for (int i = 1; i < n; ++i) { 12. if (heights[i-1] < heights[i]) { 13. leftMin[i] = i-1; 14. } else { 15. // 从小于上一个柱子的柱子开始往左查找。 16. int j = leftMin[i-1]; 17. while (j >=0) { 18. if (heights[j] < heights[i]) { 19. break; 20. } 21. j = leftMin[j]; 22. } 23. leftMin[i] = j; 24. } 25. } 26. 27. int rightMin[n]; 28. rightMin[n - 1] = n; 29. 30. for (int i = n - 2; i >= 0; --i) { 31. if (heights[i+1] < heights[i]) { 32. rightMin[i] = i+1; 33. } else { 34. // 从小于上一个柱子的柱子开始往右查找。 35. int j = rightMin[i+1]; 36. while (j < n) { 37. if (heights[j] < heights[i]) { 38. break; 39. } 40. j = rightMin[j]; 41. } 42. rightMin[i] = j; 43. } 44. } 45. 46. int maxSize = 0; 47. for (int i = 0; i < n; ++i) { 48. int H = heights[i]; 49. int L = rightMin[i] - leftMin[i] - 1; 50. maxSize = maxSize > H * L ? maxSize : H * L; 51. } 52. return maxSize; 53. } 54. };方法三：单调栈
原理和方法二一样，求包含柱子i的最大矩形。
我们建立一个栈，依次遍历每个柱子。
如果栈空入栈下标-1。
如果当前柱子高度大于栈顶下标所表示柱子的高度，当前柱子下标入栈。
如果当前柱子小于栈顶下标表示柱子的高度，弹出栈顶元素并记录下其高度。当前柱子下标减去新的栈顶下标减一（矩形的宽），然后乘以刚刚出栈柱子的高度（矩形的高）。
1. class Solution { 2. public: 3. int largestRectangleArea(vector<int>& heights) { 4. int n = heights.size(); 5. if (n == 0) { 6. return 0; 7. } 8. stack<int> st; 9. st.push(-1); 10. 11. int maxSize = 0; 12. for (int i = 0; i < n; ++i) { 13. //cout << i << " st.top: " << st.top() << endl; 14. 15. if (st.size() > 1 && heights[i] >= heights[st.top()]) { 16. //cout << "push： " << i << endl; 17. st.push(i); 18. } else { 19. while (st.size() > 1 && heights[i] < heights[st.top()]) { 20. //cout << "pop： " << st.top() << endl; 21. int H = heights[st.top()]; 22. st.pop(); 23. int L = i - st.top() - 1; 24. maxSize = maxSize > H * L ? maxSize : H * L; 25. } 26. //cout << "push： " << i << endl; 27. st.push(i); 28. } 29. } 30. 31. while (st.size() > 1) { 32. int H = heights[st.top()]; 33. st.pop(); 34. int L = n - st.top() - 1; 35. maxSize = maxSize > H * L ? maxSize : H * L; 36. } 37. 38. return maxSize; 39. } 40. };
