题解 | #直方图内最大矩形#
直方图内最大矩形
https://www.nowcoder.com/practice/bfaac4eebe5947af80912d1bcfcf2baa
#include <stack>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param heights int整型vector
* @return int整型
*/
int largestRectangleArea(vector<int>& heights) {
int result = 0 ;
heights.insert(heights.begin(), result) ;
heights.push_back(result) ;
stack<int> st ;
st.push(0) ;
for (int i = 1; i<heights.size(); i++)
{
while (!st.empty() && heights[i] < heights[st.top()])
{
int tmp = st.top() ;
st.pop();
result = max((i-st.top()-1)*heights[tmp], result) ;
}
st.push(i) ;
}
return result ;
}
};
左右找最小
投递快手等公司10个岗位
查看30道真题和解析