凉经算法题反思 | 单调栈与DP二分法

一个数组nums，大小为n，返回数组同等大小的数组，返回数组满意以下条件：

• 对于数组nums中第i个元素，找到nums从i+1到第n个元素中第一个大于nums[i]的元素，值为j，如果不存在，j=-1

例子1：

• nums =[1,2,3,3,2,6,7,2,0]
• output = [2,3,6,6,6,7,-1,-1,-1]

例子2：

• nums = [4,3,2,1,2,3,4]
• output = [-1,4,3,2,3,4,-1]

解法：这道题的时间复杂度，如果用暴力法，

的复杂度；但是如果用单调栈的算法，可以得到

的时间复杂度.

这个过程引用到了单调栈的思想。就是一个栈，里面所有元素是非严格单调递增或者单调递减的。比较好思考，就是每一个数组都要越来越小，如果不满足递减的数字，说明要从栈中取出来几个数字了。

用例子2来举例：假设现在有一个栈stack=[],前面的4个元素4，3，2，1单调递减，所以依次入栈。（这里入栈的是索引）

现在stack=[1，2，3，4]，然后因为第五个元素是2，是大于栈顶的数字1的，所以1出栈，然后对于数字1这个位置的j就是数字2，然后2入栈。这里因为要记录值和

代码简单写了写，不是很干净：

nums=[4,3,2,1,2,3,4] # 例子2
nums=[1,2,3,3,2,6,7,2,0]  # 例子1
output = [-1] * len(nums) # 这个是要返回的数组
stack = [] # 这个是单调栈
for i in range(0,len(nums)):
    # 如果栈是空的或者栈顶元素大于这个元素，入栈
    if len(stack) == 0 or nums[stack[-1]] >= nums[i]:
        stack.append(i)
        continue
    # 如果栈顶元素小于这个元素，出栈
    while len(stack)>0 and nums[stack[-1]] < nums[i]:
        index = stack.pop()
        output[index]=nums[i]
    stack.append(i)
print(output)

算法题2

还有一道题是，找到一组数据中的最长递增子数组。比如：【1，2，4，2，5，3】，最长递增子数组是【1，2，4，5】

最长递增数组Longest Increasing Sequence，下面缩写LIS。

解法：这道题如果单纯的使用动态规划方法，可以得到

的时间复杂度；如果使用二分法，可以得到

的复杂度。这道题关键在于用二分法的时候，如何找到有序数组进行查找。

这里直接讲解二分法的方法，动态规划的解法不难思考。

假设存在一个序列d[1..9] ={ 2，1 ，5 ，3 ，6，4， 8 ，9， 7}，可以看出来它的LIS长度为5。下面一步一步试着找出它。

我们定义一个序列B，然后令 i = 1 to 9 逐个考察这个序列。此外，我们用一个变量Len来记录现在最长算到多少了

首先，把d[1]有序地放到B里，令B[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1

然后，把d[2]有序地放到B里，令B[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1

接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2

再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2

继续，d[5] = 6，它在3后面，因为B[2] = 3, 而6在3后面，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？Len = 3 了噢。

第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3

第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了

第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。

最后一个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。

于是我们知道了LIS的长度为5。

下面用Python来简单写一下：

nums = [1,2,4,2,5,3]
# nums = [2,1,5,3,6,4, 8,9, 7]
B = [0] * len(nums)
Len = 0
for i in range(0,len(nums)):
    num = nums[i]
    l = 1
    r = Len
    idx = int((l + r)/2)
    while r>l:
        if B[idx] > num:
            r = idx
        else:
            l = idx+1
        idx = int((l + r)/2)
    # 找到了二分点位置，做一个简单的判断
    if num < B[idx] and num >B[idx-1] :
        B[idx]=num
    if num > B[Len]:
        Len += 1
        B[Len] = num
print(B)
print(Len)

结果是：

[0, 1, 2, 3, 5, 0]
4  # 例子1的答案
# [0, 1, 3, 4, 7, 9, 0, 0, 0]
# 5  # 例子2的答案

1，2，3，5的含义是：

• 1：如果数组长度是1，那么最小的数组中最大数就是1；
• 3：如果数组长度是3，那么有【1，2，4】，【1，2，5】，【1，4，5】，【1，2，3】四种情况，但是我们认为【1，2，3】是最好的因为，这个子数组中最大数字最小；
• 5：数组长度是4的时候，有【1,2,4,5】一种情况。

这里简单做一个总结罢了。二分法的关键在于单调数组中查找某一个数字的位置；动态规划在于寻找子优化问题；二分法的写法可以背住，到时候直接写出来就行不用动脑子。