子序列和子数组 - wenzhoullq/leetcode GitHub Wiki
dp设计为前i个的26个字母表,状态的转移为选和不选
一般子序列是O(n+m),一个for循环双指针比较
子序列最值的重点在于非连续,因此可以重排,重排后用贡献法
最少修改满足不严格递增本质就是找最长上升子序列，n - 最长上升子序列;
严格单调递增，满足如下性质: i > j ,那么 a[i] - a[j] >= i - j, 即 a[i] - i > = a[j] - i, b[i] = a[i] - i,即找b[i] 的不严格单调最长上升子序列
子数组是连续的
如果是求子数组的最值,那么都是用单调栈
这里有个值得注意的点,如果是求最小值,那么维护的是单调递增栈,如果是求最大值,则将nums[i]*-1,还是用单调递增栈
子数组还有个应用是滑动窗口，滑动窗口的本质跟单调性有点像，只要你left不断向i靠近，那么就会越会向不满足的方向靠拢
int len = nums.length,ans = 0 ,INF = Integer.MIN_VALUE;
Stack<Integer> s = new Stack<>();
s.push(INF);
for(int i = 0 ; i <= len ;i++){
int cur = i==len?INF:nums[i];//如果是最大值,则是INF:-nums[i]
while(s.size()>1&&nums[s.peek()]>cur){//如果是最大值,-nums[i]>cur
int index = s.pop();
ans+=(i-index)*(index-(s.peek()==INF?-1:s.peek()));//贡献法,求个数
ans= Math.max(ans,);//求最值
}
s.push(i);
}
return ans;- 贡献法
贡献的个数计算
int index = st.pop()
(index - s.peek()) * (i - index + 1)- 滑动窗口
- 求最值
42. 接雨水维持最小值,但是因为是淹没的,因此在处理上有些许不同
B. Mike and Feet-灵茶-1.11 也是同一个模板,主要的思考点在于长度为2的子数组的最大值和长度为1的子数组的最大值之间的关系
- 字母DP
第一个不满足集合条件的是最左边界,满足了集合条件的不断求他的最大值
分割方案有个很重要的点是初始化问题,因为连续的,第k个合法的前提是第k-1合法,如果想不明白的话。 如果是求最大值dp初始化为最小值,求最小值dp初始化为最大值,最后把有意义的dp[0][0]=0; 如果是求方案书的话,dp[0][0]=1即可 DP
枚举末端的差值 d = 1 -m ~ n , 枚举起点; 需要注意的是起点的