数据结构优化DP有前缀和、滑动窗口、树状数组、线段树、单调栈、单调队列
树状数组优化DP
300. 最长递增子序列【值域树状数组】
中等
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
朴素解法
方法一:枚举选哪个 O(n^2)
方法二:贪心+二分查找 O(nlogn)
。交换状态和状态值 dp[i]
表示末尾元素为 nums[i]
的LIS长度 == > g[i]
表示长度为 i+1
的LIS 的末尾元素的最小值
一个新员工一个老员工价值相当,老员工就可以走了,因为新员工被榨取的剩余空间更多。
class Solution {
/**
方法一:O(n^2)
定义 f[i]表示以i结尾的递增子序列的长度
转移 f[i] = f[j] + 1 , 其中j满足0<j<i && nums[j] < nums[i]
*/
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int ans = 0;
Arrays.fill(f, 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j])
f[i] = Math.max(f[i], f[j]+1);
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}
class Solution {
/**
方法二:O(nlogn)
定义 f[i] 表示长度为i的子序列末尾元素为f[i]
*/
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int len = 0;
int[] f = new int[n];
for(int x : nums){
// 二分找到 >= x 的第一个下标
int left = 0, right = len;
while(left < right){
int mid = (left + right) >> 1;
if(f[mid] < x) left = mid + 1;
else right = mid;
}
f[right] = x;
if(right == len) // 如果更新值=len,则长度+1
len++;
}
return len;
}
}
树状数组、线段树优化
具体来说,定义 f [ i ] [ j ] f[i][j] f[i][j] 表示 nums \textit{nums} nums 的前 i i i个元素中,以元素 j j j 结尾的满足条件的子序列的最长长度。
- 当 j ≠ nums [ i ] j\ne\textit{nums}[i] j=nums[i] 时, f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]。
- 当 j = nums [ i ] j=\textit{nums}[i] j=nums[i] 时,我们可以从 f [ i − 1 ] [ j ′ ] f[i-1][j'] f[i−1][j′] 转移过来,这里 j ′ < j j'<j j′<j,取最大值,得 f [ i ] [ j ] = 1 + max j ′ = 0 j − 1 f [ i − 1 ] [ j ′ ] f[i][j] = 1 + \max_{j'=0}^{j-1} f[i-1][j'] f[i][j]=1+maxj′=0j−1f[i−1][j′]
上式有一个「区间求最大值」的过程,这非常适合用线段树计算,且由于 f [ i ] f[i] f[i] 只会从 f [ i − 1 ] f[i-1] f[i−1] 转移过来,我们可以把 f f f 的第一个维度优化掉。这样我们可以用线段树表示整个 j j j 数组,在上面查询和更新。
最后答案为 max ( f [ n − 1 ] ) \max(f[n-1]) max(f[n−1]),对应到线段树上就是根节点的值。
使用滚动数组优化,可以去掉第一个条件,等价于单点修改,区间查询的问题
f[i] = f[j] + 1
- 等号左侧:单点修改
- 等号右侧:区间求max
===>树状数组、线段树维护「区间最大值」
class Solution {
/**
1. 先对nums节点离散化
2. 每次都找比当前数小的最长递增序列,不断更新结果
*/
public int lengthOfLIS(int[] nums) {
// 离散化
Set<Integer> set = new HashSet<>(); // 防止重复
for(int x : nums) set.add(x);
List<Integer> copy = new ArrayList<>(set);
Collections.sort(copy);
int res = 0;
// 值域树状数组,用树状数组维护以元素值j结尾的最长子序列长度
BIT tree = new BIT(copy.size()+1);
for(int num : nums){
// 二分找到 >= nums 的第一个下标, 查找的元素一定存在
int left = 0, right = copy.size();
while(left < right){
int mid = (left + right) >> 1;
if(copy.get(mid) < num) left = mid + 1;
else right = mid;
}
int k = right+1; // right即查找的元素,这里+1是因为树状数组下标从1开始
// 更新答案,查找以元素值(1,num-1)结尾的LIS的最大值
res = Math.max(res, (int)tree.preMax(k) + 1);
// 维护树状数组,更新以元素值(1,num)结尾的LIS的最大值
tree.update(k+1, (int)tree.preMax(k) + 1);
}
return res;
}
}
// 树状数组模板(维护前缀最大值)
class BIT {
private long[] tree;
public BIT(int n) {
tree = new long[n];
Arrays.fill(tree, Long.MIN_VALUE);
}
public void update(int i, long val) {
while (i < tree.length) {
tree[i] = Math.max(tree[i], val);
i += i & -i;
}
}
public long preMax(int i) {
long res = Long.MIN_VALUE;
while (i > 0) {
res = Math.max(res, tree[i]);
i &= i - 1;
}
return res;
}
}
2926. 平衡子序列的最大和
困难
给你一个下标从 0 开始的整数数组 nums
。
nums
一个长度为 k
的 子序列 指的是选出 k
个 下标 i0 < i1 < ... < ik-1
,如果这个子序列满足以下条件,我们说它是 平衡的 :
- 对于范围
[1, k - 1]
内的所有j
,nums[ij] - nums[ij-1] >= ij - ij-1
都成立。
nums
长度为 1
的 子序列 是平衡的。
请你返回一个整数,表示 nums
平衡 子序列里面的 最大元素和 。
一个数组的 子序列 指的是从原数组中删除一些元素(也可能一个元素也不删除)后,剩余元素保持相对顺序得到的 非空 新数组。
示例 1:
输入:nums = [3,3,5,6]
输出:14
解释:这个例子中,选择子序列 [3,5,6] ,下标为 0 ,2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以,这是一个平衡子序列,且它的和是所有平衡子序列里最大的。
包含下标 1 ,2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。
示例 2:
输入:nums = [5,-1,-3,8]
输出:13
解释:这个例子中,选择子序列 [5,8] ,下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以,这是一个平衡子序列,且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。
示例 3:
输入:nums = [-2,-1]
输出:-1
解释:这个例子中,选择子序列 [-1] 。
这是一个平衡子序列,而且它的和是 nums 所有平衡子序列里最大的。
提示:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
class Solution {
/**
nums[ij] - nums[ij-1] >= ij - ij-1
nums[i] - nums[j] >= i - j
==> nums[i] - i >= nums[j] - j
定义 b[i] = nums[i] - i
b[i] >= b[j]
==> 问题变为从 b 中选一个子序列,满足这个子序列是一个非递减的序列
求对应的元素和的最大值
a 3 3 5 6
b 3 2 4 3
定义 f[i] = 以下标 i 结尾的子序列,对应的 nums 的元素和的最大值
转移 f[i] = f[j] + nums[i], 其中 j 满足 (j < i && b[j] <= b[i])
使用值域树状数组优化,
等式左边 单点修改
等式右边 区间查询
BIT用来维护前缀最大值,设下标为x=b[i],维护的值为max(f[x], f[x-1], f[x-2]..)
实现时,需要先把nums[i] - i离散化
*/
public long maxBalancedSubsequenceSum(int[] nums) {
int n = nums.length;
int[] b = new int[n];
for(int i = 0; i < n; i++){
b[i] = nums[i] - i;
}
Arrays.sort(b);
BIT t = new BIT(b.length+1);
for(int i = 0; i < n; i++){
// j 为 nums[i]-i 离散化后的值(从 1 开始)
int j = Arrays.binarySearch(b, nums[i] - i) + 1;
long f = Math.max(t.preMax(j), 0) + nums[i];
t.update(j, f);
}
return t.preMax(b.length);
}
}
// 树状数组模板(维护前缀最大值)
class BIT {
private long[] tree;
public BIT(int n) {
tree = new long[n];
Arrays.fill(tree, Long.MIN_VALUE);
}
public void update(int i, long val) {
while (i < tree.length) {
tree[i] = Math.max(tree[i], val);
i += i & -i;
}
}
public long preMax(int i) {
long res = Long.MIN_VALUE;
while (i > 0) {
res = Math.max(res, tree[i]);
i &= i - 1;
}
return res;
}
}
线段树优化DP
300. 最长递增子序列【值域线段树】
中等
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
树状数组、线段树优化
具体来说,定义 f [ i ] [ j ] f[i][j] f[i][j] 表示 nums \textit{nums} nums 的前 i i i个元素中,以元素 j j j 结尾的满足条件的子序列的最长长度。
- 当 j ≠ nums [ i ] j\ne\textit{nums}[i] j=nums[i] 时, f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j]。
- 当 j = nums [ i ] j=\textit{nums}[i] j=nums[i] 时,我们可以从 f [ i − 1 ] [ j ′ ] f[i-1][j'] f[i−1][j′] 转移过来,这里 j ′ < j j'<j j′<j,取最大值,得 f [ i ] [ j ] = 1 + max j ′ = 0 j − 1 f [ i − 1 ] [ j ′ ] f[i][j] = 1 + \max_{j'=0}^{j-1} f[i-1][j'] f[i][j]=1+maxj′=0j−1f[i−1][j′]
上式有一个「区间求最大值」的过程,这非常适合用线段树计算,且由于 f [ i ] f[i] f[i] 只会从 f [ i − 1 ] f[i-1] f[i−1] 转移过来,我们可以把 f f f 的第一个维度优化掉。这样我们可以用线段树表示整个 j j j 数组,在上面查询和更新。
最后答案为 max ( f [ n − 1 ] ) \max(f[n-1]) max(f[n−1]),对应到线段树上就是根节点的值。
使用滚动数组优化,可以去掉第一个条件,等价于单点修改,区间查询的问题
f[i] = f[j] + 1
- 等号左侧:单点修改
- 等号右侧:区间求max
===>树状数组、线段树维护「区间最大值」
class Solution {
public int lengthOfLIS(int[] nums) {
// 离散化
Set<Integer> set = new HashSet<>(); // 防止重复
for(int x : nums) set.add(x);
List<Integer> copy = new ArrayList<>(set);
Collections.sort(copy);
N = copy.size();
int ans = 0;
for(int num : nums){
// 二分找到 >= nums 的第一个下标, 查找的元素一定存在
int left = 0, right = copy.size();
while(left < right){
int mid = (left + right) >> 1;
if(copy.get(mid) < num) left = mid + 1;
else right = mid;
}
int k = right; // num 对应的下标 k
// 查找以元素值(1,num-1)结尾的LIS的最大值
int cnt = 1 + query(root,0,N,0,k-1);
// 更新 值[k]的最大值
// 注意这里是覆盖更新,对应的模版中覆盖更新不需要累加
update(root,0,N,k,k,cnt);
ans = Math.max(ans, cnt);
}
return ans;
}
class Node {
// 左右孩子节点
Node left, right;
// 当前节点值,以及懒惰标记的值
int val, add;
}
private int N = (int) 1e9;
private Node root = new Node();
public void update(Node node, int start, int end, int l, int r, int val) {
if (l <= start && end <= r) {
node.val = val;
node.add = val;
return;
}
pushDown(node);
int mid = (start + end) >> 1;
if (l <= mid) update(node.left, start, mid, l, r, val);
if (r > mid) update(node.right, mid + 1, end, l, r, val);
pushUp(node);
}
public int query(Node node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return node.val;
pushDown(node);
int mid = (start + end) >> 1, ans = 0;
if (l <= mid) ans = query(node.left, start, mid, l, r);
if (r > mid) ans = Math.max(ans, query(node.right, mid + 1, end, l, r));
return ans;
}
private void pushUp(Node node) {
// 每个节点存的是当前区间的最大值
node.val = Math.max(node.left.val, node.right.val);
}
private void pushDown(Node node) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.add == 0) return;
node.left.val = node.add;
node.right.val = node.add;
node.left.add = node.add;
node.right.add = node.add;
node.add = 0;
}
}
单调队列优化DP
单调队列就是一种队列内的元素有单调性(单调递增或者单调递减)的队列,最优解存在队首,而队尾则是最后进队的元素。
单调队列用来维护区间最值或者降低DP的维数来减少空间及时间
利用单调队列对dp方程进行优化,可将O(n)
复杂度降至O(1)
N
维的DP,可以优化为N-1
维 !!!
单调队列适合优化决策取值范围的上、下界均单调变化的问题。
并不是所有DP都可以由单调队列优化,像最大化、最小化决策的结果,即决策具有单调性的题目可以优化。
🚀1425. 带限制的子序列和
困难
给你一个整数数组 nums
和一个整数 k
,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i]
和 nums[j]
,它们在原数组中的下标 i
和 j
满足 i < j
且 j - i <= k
。
数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。
示例 1:
输入:nums = [10,2,-10,5,20], k = 2
输出:37
解释:子序列为 [10, 2, 5, 20] 。
示例 2:
输入:nums = [-1,-2,-3], k = 1
输出:-1
解释:子序列必须是非空的,所以我们选择最大的数字。
示例 3:
输入:nums = [10,-2,-10,-5,20], k = 2
输出:23
解释:子序列为 [10, -2, -5, 20] 。
提示:
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
https://leetcode.cn/problems/constrained-subsequence-sum/solutions/220273/dpdan-diao-zhan-you-hua-xiang-jie-by-wangdh15/
class Solution {
/**
定义f[i]表示以i结尾的最大子序列和,考虑第 i 个元素选还是不选
接在后面 f[i] = max(dp[i-j] + nums[i]) , 其中 j < i 且 i-j<=k
不接,重新做起点 f[i] = nums[i]
取最大值
如果枚举所有元素作为结尾的话,时间复杂度O(nk),会超时,如何优化?
由于当前时刻只依赖于前k个时刻的状态,所以只要快速找到前k个状态中的最大子序列和即可
==> 滑动窗口求最大值
*/
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] f = new int[n]; // 定义f[i]表示以i结尾的最大子序列和
// 维护单增队列,队首为最大值,保存 (以下标为结尾的子序列和,下标)
Deque<int[]> dq = new ArrayDeque<>();
int res = nums[0];
for(int i = 0; i < n; i++){
f[i] = nums[i]; // 不接
if(!dq.isEmpty()){
// 接
f[i] = Math.max(f[i], dq.peekFirst()[0] + nums[i]);
}
res = Math.max(res, f[i]);
// 清除队列中无用的元素
while(!dq.isEmpty() && dq.peekLast()[0] <= f[i]){
dq.pollLast();
}
dq.addLast(new int[]{
f[i], i});
if(!dq.isEmpty() && dq.peekFirst()[1] == i - k)
dq.pollFirst();
}
return res;
}
}
1687. 从仓库到码头运输箱子
困难
你有一辆货运卡车,你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 boxes
和三个整数 portsCount
, maxBoxes
和 maxWeight
,其中 boxes[i] = [portsi, weighti]
。
portsi
表示第i
个箱子需要送达的码头,weightsi
是第i
个箱子的重量。portsCount
是码头的数目。maxBoxes
和maxWeight
分别是卡车每趟运输箱子数目和重量的限制。
箱子需要按照 数组顺序 运输,同时每次运输需要遵循以下步骤:
- 卡车从
boxes
队列中按顺序取出若干个箱子,但不能违反maxBoxes
和maxWeight
限制。 - 对于在卡车上的箱子,我们需要 按顺序 处理它们,卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头,那么不需要 额外行程 ,箱子也会立马被卸货。
- 卡车上所有箱子都被卸货后,卡车需要 一趟行程 回到仓库,从箱子队列里再取出一些箱子。
卡车在将所有箱子运输并卸货后,最后必须回到仓库。
请你返回将所有箱子送到相应码头的 最少行程 次数。
示例 1:
输入:boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
输出:4
解释:最优策略如下:
- 卡车将所有箱子装上车,到达码头 1 ,然后去码头 2 ,然后再回到码头 1 ,最后回到仓库,总共需要 4 趟行程。
所以总行程数为 4 。
注意到第一个和第三个箱子不能同时被卸货,因为箱子需要按顺序处理(也就是第二个箱子需要先被送到码头 2 ,然后才能处理第三个箱子)。
示例 2:
输入:boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
输出:6
解释:最优策略如下:
- 卡车首先运输第一个箱子,到达码头 1 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第二、第三、第四个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第五个箱子,到达码头 2 ,回到仓库,总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。
示例 3:
输入:boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
输出:6
解释:最优策略如下:
- 卡车运输第一和第二个箱子,到达码头 1 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第三和第四个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第五和第六个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。
示例 4:
输入:boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
输出:14
解释:最优策略如下:
- 卡车运输第一个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第二个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第三和第四个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第五个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
- 卡车运输第六和第七个箱子,到达码头 3 ,然后去码头 4 ,然后回到仓库,总共 3 趟行程。
- 卡车运输第八和第九个箱子,到达码头 1 ,然后去码头 5 ,然后回到仓库,总共 3 趟行程。
总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。
提示:
1 <= boxes.length <= 105
1 <= portsCount, maxBoxes, maxWeight <= 105
1 <= portsi <= portsCount
1 <= weightsi <= maxWeight
https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports/solutions/2006470/by-lcbin-xwzl/
class Solution {
/**
定义f[i]表示运送前i个箱子需要的最小行程次数
转移,枚举上一次运送的状态,包括[1,2,3...maxBoxeds]个箱子,i可以从j转移过来
f[i] = f[j-1] + cost[j, i] (i - maxB+1 <= j <= i)
cost[j, i] 表示第k~第i个箱子的行程次数
枚举所有以i结尾的行程会超时 O(n^2),如何优化?
实际上我们是要在[i-maxBoxeds,..i-1]这个窗口内找到一个j,
使得f[j] - cost[j]的值最小,
问题变为求滑动窗口的最小值
如何优化码头i到j的行程数?取决于相邻两个码头是否相等
我们可以通过前缀和,计算出码头之间的行程数,再加上首尾两趟行程,就能O(1)计算
重量同理
*/
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
long[] ws = new long[n+1];
int[] cs = new int[n];
for(int i = 0; i < n; i++){
int p = boxes[i][0], w = boxes[i][1];
ws[i+1] = ws[i] + w;
if(i < n-1){
cs[i+1] = cs[i] + (p != boxes[i+1][0] ? 1 : 0);
}
}
int[] f = new int[n+5];
Deque<Integer> dq = new ArrayDeque<>();
dq.add(0);
for(int i = 1; i <= n; i++){
while(!dq.isEmpty() && (i - dq.peekFirst() > maxBoxes ||
ws[i] - ws[dq.peekFirst()] > maxWeight)){
dq.pollFirst();
}
if(!dq.isEmpty()){
f[i] = cs[i-1] + f[dq.peekFirst()] - cs[dq.peekFirst()] + 2;
}
if(i < n){
while(!dq.isEmpty() && f[dq.peekLast()] - cs[dq.peekLast()] >= f[i] - cs[i]){
dq.pollLast();
}
dq.addLast(i);
}
}
return f[n];
}
}