单调栈--poj2559 Largest rectangle in a Histogram

2024-01-14 06:38

本文主要是介绍单调栈--poj2559 Largest rectangle in a Histogram,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一个直方图里,求最大的矩形。类似2 1 4 5 1 3 3

做完poj2796,再回来看,其实就是区间最小值乘区间长度吧。

解释见 http://blog.csdn.net/alongela/article/details/8230739

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stack>

using namespacestd;

const int maxn =100000 +5;

int h[maxn],dep[maxn];

typedef pair<int,int> pr;//记录矩形的高度,宽度

int main()

{

    int n;

    while(scanf("%d",&n) !=EOF && n)

    {

        memset(h,0,sizeof(h));

        memset(dep,0,sizeof(dep));

        for (int i =1; i <= n; i ++) {

            scanf("%d",&h[i]);//1e9

        }

        stack<pr> stk;

        longlong area =0;

        int t =0;

        for (int i =1; i <= n; i ++) {

                while (!stk.empty() && stk.top().first >= h[i]) {

                    area = max(area,(longlong)stk.top().first * (stk.top().second + t));

                    t += stk.top().second;

                    stk.pop();

                }

                 stk.push({h[i],t +1});

            t = 0;

        }

        t = 0;

        while (!stk.empty()) {

            area = max(area,(longlong)stk.top().first * (stk.top().second + t));

            t += stk.top().second;

            stk.pop();

        }

        printf("%lld\n",area);

    }

    return0;

}

这篇关于单调栈--poj2559 Largest rectangle in a Histogram的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/604249

相关文章

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

双指针(5)_单调性_有效三角形的个数

个人主页:C++忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创 双指针(5)_单调性_有效三角形的个数 收录于专栏【经典算法练习】 本专栏旨在分享学习C++的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 1. 题目链接: 2.题目描述 : 3.解法 :     解法一(暴力枚举) :     算法思路 :     代码展示 : 暴力枚

机器学习模型中的因果关系:引入单调约束

单调约束是使机器学习模型可行的关键,但它们仍未被广泛使用欢迎来到雲闪世界。 碳ausality 正在迅速成为每个数据科学家工具包中必不可少的组成部分。 这是有充分理由的。 事实上,因果模型在商业中具有很高的价值,因为它们为“假设”情景提供了更可靠的估计,特别是在用于做出影响业务结果的决策时。 在本文中,我将展示如何通过简单的更改(实际上添加一行代码)将传统的 ML 模型(如随机森林、L

单调栈的实现

这是C++算法基础-数据结构专栏的第二十四篇文章,专栏详情请见此处。 引入         单调栈就是满足单调性的栈结构,它最经典的应用就是给定一个序列,找出每个数左边离它最近的比它大/小的数。         下面我们就来讲单调栈的实现。 定义          单调栈就是满足单调性的栈结构,也就是说,其中的元素具有单调性,但是存储的方法和基本操作与栈一样。 过

[LeetCode] 215. Kth Largest Element in an Array

题:https://leetcode.com/problems/kth-largest-element-in-an-array/description/ 题目 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not th

单调队列(专项复习)

P1886 滑动窗口 /【模板】单调队列    题目思路:单调队列模版题,每次都输出队列中的第一个元素。以此维护队列中元素序号的单调性,得到结果。只是比较判断,时间复杂度很小。相等的值也要挤掉。最大值同理。 代码实现: #include<bits/stdc++.h>using namespace std;typedef long long ll;#define N 3000005

【每日一题】LeetCode 84.柱状图中最大的矩形(栈、数组、单调栈)

【每日一题】LeetCode 84.柱状图中最大的矩形(栈、数组、单调栈) 题目描述 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 这个题目和接雨水非常类似 点击跳转接雨水 LeetCode 40.接雨水 输入示例 输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的

[算法]单调栈解法

目录 739. 每日温度 - 力扣(LeetCode)  42. 接雨水 - 力扣(LeetCode) 84. 柱状图中最大的矩形 - 力扣(LeetCode) 739. 每日温度 - 力扣(LeetCode)  解法: 通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。 1.在本题中,其实就是,找到一个元素右边

力扣刷题单调栈

单调栈 No.1 739.每日温度. - 力扣(LeetCode) 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 示例 1: 输入: temperatures = [73,74,75,71,69,72,76,7