|
|
题意：
给你n个数hi，你刚开始在第1个数的位置，你需要跳到第n个数的位置。
1、对于i、j(i<j) 如果满足
max(hi+1,…,hj?1)<min(hi,hj)
max(hi,hj)<min(hi+1,…,hj?1)
那么就可以从i直接一步跳到j位置
2、如果j=i+1，那么也可以直接跳过去
问你从第一个位置跳到第n个位置，最少需要跳多少次
题解：
我们设dp表示：从第一个位置跳到第i个位置最小需要跳多少次
我们最重要的就是找在[1,i-1]这个区间内的k，哪个位置可以跳到i位置以使得dp尽可能小。如果暴力查找的话，那么复杂度就是O(n*n)，看一下数据就知道TLE
那我们就要用一种数据结构来使得找这个k，这里我们使用栈，为什么不使用队列，因为如果满足
max(hk+1,…,hi-1)<min(hk,hi)
max(hk,hi)<min(hk+1,…,hi-1)
就可以从k一步跳到i，我们使用单调队列那么就是从头开始了。
我们维护两个单调栈，一个非严格递增，另一个非严格递减
我们在这里讨论非严格单调递增栈的维护过程：
如果一个数vi在放入栈之前，判断得知hi>=h[r.top],那么就可以从r.top位置跳到i位置。
这个时候有一个问题，如果你把栈中的一些元素pop掉了，但是这些元素还可以更新大于i的位置的dp值 这个时候会影响最后的结果吗？
其实是不会影响的，因为如果hk在hi进行栈之前被pop掉了，那么hk肯定是小于hi的。如果hk可以更新hj的信息（i<j） 那么vk和vj中那个大的肯定会小于min（vk+1,vk+2...vj-1）。 那么这个时候我们看我们维护的另一个非严格下降序列，它会替我们考虑这个问题的
所以这样实现起来其实是没有问题的
代码：
|
|
发表于 2022-5-8 17:02:44
