单调性问题思考简记（仅笔记）

科技起源

2026-05-27 20:23:55

发布于：北京

8阅读

0回复

0点赞

我才六年级，我还不太熟悉dp呢，喷可以，但喷轻点谢谢
还有本篇未完全使用标准的Markdown规范文章模板及LaTeX，不要骂！

单调性问题简介

先从一道经典单调性问题：最长上升子序列开始说起
很多人可能觉得：“为什么这种文章中会出现如此简单的题目？” ~~你等会就知道了~~

先看最经典写法：

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1111;
int a[N];
int dp[N];
// 特别需要注意的是，dp[i]代表“以第i个数为结尾的最长上升子序列长度”

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        dp[i] = 1;
    }
    for (int i = 2;i <= n;i++){
        for (int j = 1;j < i;j++){
            if (a[j] >= a[i]) continue;
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int mx = INT_MIN;
    for (int i = 1;i <= n;i++){
        mx = max(mx, dp[i]);
    }
    cout << mx;
    
    return 0;
}

时间复杂度： $O(n^2)$
这个时间复杂度是不太理想的
我们今天的方法就是要将代码的时间复杂度优化到 $O(n log n)$
实际上，绝大多数优化方法优化的都是时间复杂度/空间复杂度

那如何将代码代码的时间复杂度优化到 $O(n log n)$ 呢？

先回顾问题：

输入n个数（对于单调性优化类题来讲， $n \le 10^6$ ），输出其最长上升子序列长度

用二分
你想啊，既然都是“单调性问题”了，那不自然可以和二分结合吗？

dp含义的更改

dp数组此时必须要包含结尾数字信息（xxx情况下，结尾数字是…）
要从dp[i]表示以第i个数为结尾的最长上升子序列长度
转变为
dp[i] = x表示最长上升子序列长度为 $i$ 的情况下，结尾数字是 $x$
还不对！结尾数字可能有很多，因此要改成
dp[i] = x表示最长上升子序列长度为 $i$ 的情况下，结尾数字最小是 $x$

Q1：为什么是“结尾数字最小是 $x$ ”？
A1：因为结尾数字越多，前面数字的可能性越大；可能性越大，最长上升子序列的长度就有可能越长

状态转移方程的更改

我们考虑可能造成的影响:

要么就是使最长上升子序列长度+1
那么我们就需要一个变量len，记录当前最长上升子序列的长度，并更新
也就是当 $a_i > dp_{len}$ 时，要进入这种情况

要么就是优化前面的最长上升子序列
也就是当 $a_i < dp_{len}$ 时，要进入这种情况
这时便于理解，举个栗子🌰：
$A = [1,\ 2,\ 5,\ 8,\ 4,\ 7]$
到 $4$ 这一项时，无法显然无法替换 $8$ ，可以替换 $5、2、1$ ，但替换 $2、1$ 是没有用的
所以如果 $dp_{j_1},\ dp_{j_2}, \cdots dp_{j_n} > a[i]$ ，此时要替换最小的那个
因为替换其他的是没有用的，甚至会不合法（就是例子中的 $4$ 只能替代 $5$ ，不能替代 $8$ ，要不然会不合法）
此时需要二分查找第一个比 $a_i$ 大的数字

Q1：为什么此时符合单调性？
A1：因为dp的定义促使了成为符合单调性的队列

Q2：为什么二分直接找到第一位大于 $a_i$ 的位置idx就可以直接 $dp_{idx}=a_i$
A2：因为本质上第一位大于 $a_i$ 的位置idx就是 dp数组前idx项，更改dp前idx项的最小值为 $a_i$ 即可

输出答案的更改

既然已经有一个变量len了，直接输出即可

总结

所以更改后的 $O(nlogn)$ 代码

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 5555;
int a[N], dp[N];
int len = 0;

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for (int i = 1;i <= n;i++){
		if (a[i] > dp[len]){
			len++;
			dp[len] = a[i];
		} else {
			/*
			int l = 0, r = len;
			while(l < r){
				int mid = (l + r) / 2;
				if (dp[mid] >= a[i]){
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			*/
			// 更简便的写法：
			int l = lower_bound(dp + 1, dp + len + 1, a[i]) - dp;
			dp[l] = a[i];
		}
	}
	cout << len;
	
	return 0;
}