当前位置:网站首页>Sword finger offer II 039 Maximum rectangular area of histogram
Sword finger offer II 039 Maximum rectangular area of histogram
2022-07-06 05:19:00 【Small white yards fly up】
Summary
Monotonic stack , It's hard to think .
subject
Given an array of nonnegative integers heights , The numbers in the array are used to represent the height of each column in the histogram . Each column is adjacent to each other , And the width is 1 .
In this histogram , The maximum area of a rectangle that can be outlined .
link :https://leetcode.cn/problems/0ynMMM
Ideas
Or use monotone stack . You'll find that , The core of these questions , All use a monotonous stack , Then when traversing the array , Compare the current element with the top element , Always ensure that the top element of the stack is the largest ( Or the smallest ).
The core points of solving this problem are as follows :
- Centered on the height of a column , Spread to both sides to find the boundary . Find a pillar shorter than this one , It's the boundary . At this time, the area can be calculated according to the height of the column and the boundary length .
- Use a monotonic stack whose top is larger than the bottom , To maintain the left boundary .
- If the current element traversed is larger than the top element , The stack .
- If the current element traversed is smaller than the top element , Then the top element of the stack is column , And the position of the current element , Is the rightmost boundary . And because it's a monotonous stack , So the elements below the top of the stack , When the top of the stack is a column , The rightmost boundary .
- Push stack out of stack , Compare the size relationship between the new stack top and the current element , Repeat the logic of the first two
- Traversal complete , Then put the elements that still exist in the stack , Do further calculations . Only when the rightmost column is higher than the front column , That's what happens . So the right boundary at this time , Is the right boundary of the array .
solution : Monotonic stack
Code
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
// It is convenient to deal with boundary problems
stack.push(-1);
int result = 0;
for (int i = 0; i < heights.length; i++) {
int current = heights[i];
while (stack.peek() != -1 && heights[stack.peek()] > current) {
// Get the subscript of the top of the stack element and remove the top of the stack element
int height = heights[stack.pop()];
int with = i - stack.peek() - 1;
result = Math.max(result, height * with);
}
stack.push(i);
}
// Handle the remaining boundaries in the stack . At this time, the right boundary must be the rightmost end of the array
while (stack.peek()!=-1) {
result = Math.max(result, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return result;
}
Submit results
P.S. The animation of this solution is great :https://leetcode.cn/problems/0ynMMM/solution/hua-luo-yue-que-wo-zhen-de-zhen-de-nu-li-ohjt/
边栏推荐
- [untitled]
- Fiddler installed the certificate, or prompted that the certificate is invalid
- [buuctf.reverse] 159_ [watevrCTF 2019]Watshell
- Three.js学习-光照和阴影(了解向)
- UCF (2022 summer team competition I)
- Three methods of Oracle two table Association update
- 你需要知道的 TCP 三次握手
- 【OSPF 和 ISIS 在多路访问网络中对掩码的要求】
- Postman assertion
- 注释、接续、转义等符号
猜你喜欢
Fiddler installed the certificate, or prompted that the certificate is invalid
idea一键导包
指針經典筆試題
Ora-01779: the column corresponding to the non key value saving table cannot be modified
F12 solve the problem that web pages cannot be copied
Codeforces Round #804 (Div. 2)
Yolov5 tensorrt acceleration
从0到1建设智能灰度数据体系:以vivo游戏中心为例
February 12 relativelayout
What are the advantages of the industry private network over the public network? What specific requirements can be met?
随机推荐
Building intelligent gray-scale data system from 0 to 1: Taking vivo game center as an example
Extension of graph theory
[leetcode daily question] number of enclaves
Fiddler installed the certificate, or prompted that the certificate is invalid
Hyperledger Fabric2. Some basic concepts of X (1)
Questions d'examen écrit classiques du pointeur
Quelques conseils communs sur l'inspecteur de l'unit é, généralement pour les extensions d'éditeur ou d'autres
05. 博客项目之安全
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Summary of redis basic knowledge points
初识CDN
UCF (summer team competition II)
关于Unity Inspector上的一些常用技巧,一般用于编辑器扩展或者其他
Collection + interview questions
HAC集群修改管理员用户密码
你需要知道的 TCP 三次握手
Easy to understand I2C protocol
Vulhub vulnerability recurrence 69_ Tiki Wiki
Knowledge points of circular structure
Tetris