首页 > 其他分享 >剑指 Offer II 039. 直方图最大矩形面积

剑指 Offer II 039. 直方图最大矩形面积

时间:2023-05-29 17:44:54浏览次数:60  
标签:下标 Offer int top stk II 直方图 ans heights

题目链接:剑指 Offer II 039. 直方图最大矩形面积

方法:单调栈

解题思路

  • 以直方图中的某一条为高的最大(面积)矩形的宽度为 \(r - l + 1\),其中 \(r\) 表示在其右边第一个小于(或等于)当前高度的下标,\(l\) 表示在其左边第一个小于当前高度下标。
  • \(l\),\(r\) 可以利用单调栈在 \(O(1)\) 时间获取:
    • 单调栈存储单调递增的下标;
    • 若当前下标对应的高度小于栈顶下标对应的高度,则当前下标就是栈顶下标的 \(r\);
    • 次栈顶下标就是栈顶下标的 \(l\);
  • 计算以每个下标为高的矩形面积最大值,答案取其中的最大值。
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);
        int ans = 0, n = heights.size();
        for (int i = 0; i < n; i ++ ) {
            while (stk.top() != -1 && heights[stk.top()] >= heights[i]) {
                int h = heights[stk.top()];
                stk.pop();
                ans = max(ans, h * (i - stk.top() - 1));
            }
            stk.push(i);
        }
        while (stk.top() != -1) {
            int h = heights[stk.top()];
            stk.pop();
            ans = max(ans, h * (n - stk.top() - 1));
        }
        return ans;
    }
};

复杂度分析

时间复杂度:\(O(n)\);
空间复杂度:\(O(n)\)。

标签:下标,Offer,int,top,stk,II,直方图,ans,heights
From: https://www.cnblogs.com/lxycoding/p/17441173.html

相关文章

  • 动态规划:剑指 Offer 60. n个骰子的点数
    题目描述:把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案,其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。 方法:动态规划     classSolution{pub......
  • Problem B: 类的初体验(II)
    HomeWebBoardProblemSetStandingStatusStatisticsProblemB:类的初体验(II)TimeLimit:1Sec  MemoryLimit:128MBSubmit:715  Solved:653[Submit][Status][WebBoard]Description定义一个类Data,只有一个double类型的属性和如下3个方法:1. 带1......
  • 剑指 Offer 06. 从尾到头打印链表
    剑指Offer06.从尾到头打印链表</br></br>题目:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例:输入:head=[1,3,2]输出:[2,3,1]限制:0<=链表长度<=10000</br></br>思路一:使用reverse函数完成链表的逆序打印。我们通过遍历将链表中的值插......
  • 剑指 Offer 57 - II. 和为s的连续正数序列
    题目描述:输入一个正整数target,输出所有和为target的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。 方法:滑动窗口(双指针) classSolution{publicint[][]findContinuousSequence(inttarget){inti=1,j......
  • IIS短文件名暴力枚举漏洞利用工具(IIS shortname Scanner)
    脚本可以测试对应的URL是否存在漏洞,若存在漏洞,则猜解文件夹下所有的短文件名:包括文件和文件名。网上早前已经有公开的工具了:https://code.google.com/p/iis-shortname-scanner-poc/我没有参考他的代码。自己用python实现了一个漏洞利用脚本。简单测试,发现比上面的POC能猜解到更......
  • 63. Unique Paths II刷题笔记
    问题描述主要是稀奇古怪的边界条件,例如左上角是1,最左边和最上边是1,有多个1,输入为行,或者列classSolution:defuniquePathsWithObstacles(self,obstacleGrid:List[List[int]])->int:m=len(obstacleGrid)n=len(obstacleGrid[0])dp=[0]*m......
  • 107. Binary Tree Level Order Traversal II刷题笔记
    问题描述自底向上层序搜索python代码#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:deflevelOrd......
  • 52. N-Queens II刷题笔记
    回溯算法,参考该题解classSolution:deftotalNQueens(self,n:int)->int:diag1=set()diag2=set()usedCols=set()returnself.helper(n,diag1,diag2,usedCols,0)defhelper(self,n,diag1,diag2,usedCols,......
  • 剑指Offer58-II.左旋转字符串——学习笔记
    题目:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。示例1:输入:s="abcdefg",k=2输出:"cdefgab"示例2:输入:s="lrloseum......
  • 剑指 Offer 24. 反转链表
    剑指Offer24.反转链表</br></br>题目:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。示例:输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL限制:0<=节点个数<=5000</br></br>思路一:双指针法:可以通过改变链表中节点的next指针的指......