描述

思路

单调栈的思路是如下图的例子
维持一个单调递增的栈,当新的元素(当前元素)大于栈顶元素的时候,就说明以栈顶元素为长的长方形,其宽度最多可以达到当前元素前一个位置。这样子看就可以理解下面的代码了。
image.png

代码

  1. class Solution
  2. {
  3. public:
  4. int largestRectangleArea(vector<int>& heights) {
  5. stack<int> stk;
  6. stk.push(-1);
  7. int max_area = 0;
  8. for (size_t i = 0; i < heights.size(); i++) {
  9. while (stk.top() != -1 and heights[stk.top()] >= heights[i]) {
  10. int current_height = heights[stk.top()];
  11. stk.pop();
  12. int current_width = i - stk.top() - 1;
  13. max_area = max(max_area, current_height * current_width);
  14. }
  15. stk.push(i);
  16. }
  17. while (stk.top() != -1) {
  18. int current_height = heights[stk.top()];
  19. stk.pop();
  20. int current_width = heights.size() - stk.top() - 1;
  21. max_area = max(max_area, current_height * current_width);
  22. }
  23. return max_area;
  24. }
  25. // int largestRectangleArea(vector<int>& heights)
  26. // {
  27. // // use deque, store index of heights
  28. // // the elements of deque is monothly increasing, front is the smallest and back is the largest
  29. // list<pair<int, int>> m_deque;
  30. // int res = heights[0];
  31. // m_deque.push_back(make_pair(0,0));
  32. // for(int i = 1; i < heights.size(); i++)
  33. // {
  34. // res = max(res, heights[i]);
  35. // bool flag = true;
  36. // for(auto it : m_deque)
  37. // {
  38. // int index = it.first;
  39. // int pre_index = it.second;
  40. // res = max(res, min(heights[i], heights[index]) * (i - pre_index + 1));
  41. // if(heights[i] <= heights[index])
  42. // {
  43. // flag = false;
  44. // while(m_deque.back().first != index)
  45. // {
  46. // m_deque.pop_back();
  47. // }
  48. // auto back = m_deque.back();
  49. // m_deque.pop_back();
  50. // m_deque.push_back(make_pair(i, back.second));
  51. // break;
  52. // }
  53. // }
  54. // if(flag)
  55. // {
  56. // m_deque.push_back(make_pair(i, i));
  57. // }
  58. // }
  59. // return res;
  60. // }
  61. };