LeetCode
  • Introduction
  • 第一章: 基本结构
    • 1.1 数组
      • Q11. Container With Most Water
      • Q16. 3Sum Closest
      • Q118. Pascal's Triangle
      • Q119. Pascal's Triangle II
      • Q120. Triangle
      • Q134. Gas Station
    • 1.2 链表
      • Q2: Add Two Numbers
      • Q19. Remove Nth Node From End of List
      • Q82. Remove Duplicates from Sorted List II
      • Q86: Partition List
      • Q92. Reverse Linked List II
      • Q141. Linked List Cycle
      • Q142. Linked List Cycle II
      • Q147. Insertion Sort List
      • Q160. Intersection of Two Linked Lists
      • Q206. Reverse Linked List
    • 1.3 哈希
      • Q1: Two Sum
      • Q3. Longest Substring Without Repeating Characters
    • 1.4 堆栈
      • Q84: Largest Rectangle in Histogram
      • Q155. Min Stack
      • Q20. Valid Parentheses
      • Q225. Implement Stack using Queues
      • Q232. Implement Queue using Stacks
    • 1.5 树
      • Q94. Binary Tree Inorder Traversal
      • Q100. Same Tree
      • Q101. Symmetric Tree
      • Q102. Binary Tree Level Order Traversal
      • Q103. Binary Tree Zigzag Level Order Traversal
      • Q104. Maximum Depth of Binary Tree
      • Q105. Construct Binary Tree from Preorder and Inorder Traversal
      • Q106. Construct Binary Tree from Inorder and Postorder Traversal
      • Q107. Binary Tree Level Order Traversal II
      • Q108. Convert Sorted Array to Binary Search Tree
      • Q109. Convert Sorted List to Binary Search Tree
      • Q110. Balanced Binary Tree
      • Q111. Minimum Depth of Binary Tree
      • Q112. Path Sum
      • Q113. Path Sum II
      • Q114. Flatten Binary Tree to Linked List
      • Q116. Populating Next Right Pointers in Each Node
      • Q117. Populating Next Right Pointers in Each Node II
      • Q129. Sum Root to Leaf Numbers
      • Q144. Binary Tree Preorder Traversal
    • 1.6 图
    • 1.7 二进制
      • Q89. Gray Code
      • Q136. Single Number
      • Q137. Single Number II
      • Q191. Number of 1 Bits
      • Q190. Reverse Bits
    • 1.8 字符串
      • Q5. Longest Palindromic Substring
      • Q14. Longest Common Prefix
      • Q125. Valid Palindrome
  • 第二章: 动态规划
    • Q85: Maximal Rectangle
    • Q91. Decode Ways
    • Q121. Best Time to Buy and Sell Stock
    • Q198. House Robber
  • 第三章: 递归
    • Q17. Letter Combinations of a Phone Number
    • Q78. Subsets
    • Q86. Scramble String
    • Q90: Subsets II
  • 第四章:贪心
    • Q122. Best Time to Buy and Sell Stock II
  • 第五章:分治法
  • 第六章:数学
    • Q6. ZigZag Conversion
    • Q7. Reverse Integer
    • Q9. Palindrome Number
    • Q168. Excel Sheet Column Title
    • Q171. Excel Sheet Column Number
  • 第七章:查找
    • Q15. Three Sum
    • Q167. Two Sum II
    • Q169. Majority Element
  • 第八章:排序
Powered by GitBook
On this page
  • 分析:
  • 举例:
  • C++实现:

Was this helpful?

  1. 第一章: 基本结构
  2. 1.4 堆栈

Q84: Largest Rectangle in Histogram

Previous1.4 堆栈NextQ155. Min Stack

Last updated 5 years ago

Was this helpful?

直达:

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 =10unit.

For example, Given heights =[2,1,5,6,2,3], return10.

分析:

  1. 计算以每个bar为高的最大矩形区域面积,返回最大值;

  2. 如果bar的高度逐渐增高,则围城的面积逐渐增大,不需要计算;

  3. 如果bar的高度开始递减(设为k),则要计算递减之前的最大面积,为了避免重复计算,从右向左计算至小于height[k]的时候停止计算即可;

  4. 可在数组后面添加一个高度为0的bar,用于辅助清空临时堆栈;

  5. 从左向右遍历,再从右向左计算面积,明显用堆栈存储效率更高,由于可以通过下标访问到高度,存储下标即可。

举例:

  1. 索引i=0, height[0] = 2,堆栈为空,直接将2的下标0压栈,i++;

  2. i=1,height[1]=1 < 2, 开始从右向左计算面积;

    1. i=0的bar的面积是0的长度1乘以高度2,即为2,保存res=2;

    2. 堆栈为空,停止弹出。

  3. i=1, 堆栈为空,将i=1压栈, i++;

  4. i=2, height[i]=5>height[stk.top()]=1, 将i=2压栈,i++;

  5. i=3, height[i]=6>height[stk.top()]=5. 将i=3压栈,i++, 此时,stk=[1,2,3];

  6. i=4, 此时height[i]=2<height[stk.top()], 开始从右向左计算面积;

    1. 弹出栈顶h=stk.top()=3, stk.pop(), 此时的矩形区域的长是(i-stk.top()-1), 高是height[h], area = (i-stk.top()-1)*height[h] = 6, res更新为6;

    2. 弹出栈顶h=stk.top()=2, area = (i-stk.top()-1) * height[h] = (4-1-1)*5 = 10.

  7. i=4, stk.top()=1 < height[i]=2, 4入栈,i++;

  8. i=5, 5入栈,i++, 此时stk=[1,4,5];

i=6, 遍历到添加的0高度,开始从右向左计算面积,并清空堆栈;

  1. h=stk.top()=5, stk.pop(), area = (6-stk.top()-1) * height[5] = 3, stk = [1,4], res = 10;

  2. h=stk.top()=4, stk.pop(), area = (6-stk.top()-1) * height[4] = 8, stk = [1], res = 10;

  3. h=stk.top()=1, stk.pop(), 堆栈为空,area = (i)*height[h] = 6, res = 10;

  4. 由此可以返回最大值10

C++实现:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); i++){
            if(stk.empty() || heights[i] > heights[stk.top()]){
                stk.push(i);
            }else{
                int h = stk.top();
                stk.pop();
                res = max(res, (stk.empty()?i:i-stk.top()-1) * heights[h]);
                i--;
            }
        }
        return res;
    }
};
https://leetcode.com/problems/largest-rectangle-in-histogram/description/