搜索结果
查询Tags标签： 单调，共有 99条记录-
单调栈基础知识
单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。 单…
2022/9/16 23:18:30 人评论 次浏览 -
现在是 2022 年了，你不知道什么是单调栈和单调队列吗？ （下）
报名金石计划第一次挑战——分享10万奖池，这是我的第2篇文章， 点击查看活动详情 从上面继续， 现在是 2022 年了，你不知道什么是单调栈和单调队列吗？ （上）——掘金（juejin.cn） .今天我们将讨论什么是单调堆栈。 介绍 阅读本文后，您将获得：什么是单调栈 单调栈可…
2022/9/11 6:23:22 人评论 次浏览 -
单调栈-下一个更大元素
单调栈使用满足如下：输入:nums1=[4,1,2],nums2=[1,3,4,2].输出:[-1,3,-1]解释:对于num1中的数字4 ，你无法在第二个数组中找到下一个更大的数字，因此输出-1。对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3 。对于num1中的数字2，第二个数组中没有下一个…
2022/9/8 23:56:08 人评论 次浏览 -
优化dp
单调队列优化dp 单调队列单调队列是一种特殊的双端队列，其内部元素具有单调性。常见有最大队列和最小队列两种单调队列，其内部元素分别是单调递减和单调递增的。 支持两种操作 -插入：如果新元素从队尾插入后会破坏其单调性，则删除队尾元素，直到插入后不再破坏单调性为…
2022/9/8 23:53:18 人评论 次浏览 -
CF1550C 题解
前言 题目传送门！ 更好的阅读体验？ 比赛时，这题写了一个 \(O(n^3)\) 算法，然后就过了。 以为是数据水，实际上可以证明时间复杂度是 \(O(n)\) 的。 思路 关键是一个结论：当 \(i < j < k\) 时，若 \(a_i, a_j, a_k\) 单调不降或单调不升，则三元组 \((a_i, i), …
2022/8/27 23:22:49 人评论 次浏览 -
重修 斜率优化 Dp
斜率单调暴力移指针 斜率不单调二分找答案 \(x\) 坐标单调开单调队列 \(x\) 坐标不单调开平衡树 / cdq分治P4072 [SDOI2016]征途 我们要求方差最小，而总和不变，等价于要每天走的路程平方和最小。 设 \(s(i)\) 表示前 \(i\) 段路的距离总和。 首先我们有一个 naive 的 \(…
2022/8/15 23:26:45 人评论 次浏览 -
目录
一：基础算法 快速排序（求第k小的数） 归并排序（逆序对数量） 高精度 前缀和&差分 双指针 贪心 递推 递归 二分 倍增 位运算 二：数据结构 链表 单调栈 单调队列 哈夫曼树 堆 ST表 并查集 树状数组 线段树 字典树（trie树） 哈希表 笛卡尔树 基环树 平衡树 三：搜索…
2022/8/6 23:27:09 人评论 次浏览 -
单调栈
单调栈 ACWing 803 给定一个长度为 NN 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1−1。 输入格式 第一行包含整数 NN，表示数列长度。 第二行包含 NN 个整数，表示整数数列。 输出格式 共一行，包含 NN 个整数，其中第 ii 个数表示第 ii 个数的左…
2022/7/14 6:20:11 人评论 次浏览 -
算法-19可见的山峰对数量(单调栈)
描述一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时…
2022/7/5 1:20:07 人评论 次浏览 -
【926. 将字符串翻转到单调递增】动态规划
class Solution {public int minFlipsMonoIncr(String s) {int len = s.length();int[][] dp = new int[len][2];if (s.charAt(0) == 0) {dp[0][0] = 0;dp[0][1] = 1;} else {dp[0][1] = 0;dp[0][0] = 1;}for (int i = 1; i < len; i++) {if (s.charAt(i) == 1) {dp[i]…
2022/6/11 23:51:57 人评论 次浏览 -
洛谷P2627 [USACO11OPEN]Mowing the Lawn G （单调队列优化DP）
一道单调队列优化DP的入门题。 f[i]表示到第i头牛时获得的最大效率。 状态转移方程：f[i]=max(f[j-1]-sum[j])+sum[i] ,i-k<=j<=i。j的意义表示断点，因为不能连续安排超过k只牛，肯定要在中间断开一处。 max中f[j-1]-sum[j]只和j相关，我们可以对其做递减单调队列，…
2022/6/11 23:50:52 人评论 次浏览 -
cf1482 E. Skyline Photo
题意： 给定一排 n 个点，每个点有 \(h_i\) 和 \(v_i\)。把它们划分成任意数量的连续段，每个点仅属于一段，每段的价值等于段中 \(h\) 最小的点的 \(v\) 值。求最大价值和 \(h_i\) 为 1~n 的一个排列，\(-1e9\le v_i\le 1e9\) 思路： 用到单调（递增）栈的两个性质：1. 栈…
2022/5/30 23:20:15 人评论 次浏览 -
单调栈
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。 输入格式 第一行包含整数 N，表示数列长度。 第二行包含 N 个整数，表示整数数列。 输出格式 共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存…
2022/4/21 6:15:10 人评论 次浏览 -
「JOISC 2022 Day4」鱼 2
考虑怎么样的鱼能取得最后的胜利，它一定是不断贪心地往两边吃，能吃就吃。 实现以上过程的一个朴素想法是，对左右两边分别维护”有效“单调栈，暴力扫一遍。 考虑用线段树维护上述过程，思考如何合并区间信息。 假设有 \(x\) 条鱼能在左子树中吃完所有的鱼，那么加入右区…
2022/4/15 23:18:00 人评论 次浏览 -
洛谷P4147 玉蟾宫 （单调栈）
要求我们去找一个最大矩形面积。 单调栈做法（和P1950 长方形那道题类似（一模一样））。1 #include<bits/stdc++.h>2 using namespace std;3 char M[1010][1010];4 int n,m,h[1010],l[1010],r[1010];5 int s[1010],top;6 7 void ddzl(){8 top=0;9 for(int …
2022/4/15 23:14:56 人评论 次浏览
