32. Longest Valid Parentheses

Leetcode String Dynamic Programming

题目

[Hard]

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

中文题目

实现下一个排列，将排列中的数字重新排列成字典序中的下一个更大的排列。

如果这样的重新排列是不可能的，它必须重新排列为可能的最低顺序（即升序排序）。

重排必须在原地，不分配额外的内存。

以下是一些示例，左侧是输入，右侧是输出：

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路

做题目前，应该先理解排列permuation的概念，以及next permutation的含义。例如题目例子里的1，2，3的全排列，依次是：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

next permuation的含义是从上面的第$i$行到第$i+1$行，如果是最后一行，则为第1行。

首先，应该了解到在前面变换数字，会导致排列增加很多，例如从1 2 3到 3 2 1。所以既然要找到比原来的数的排列大一点的数，自然是从后往前找。如果数组从尾到前是增加的，那么就表明，从尾到前增加的这几个数字已经是最大的排列了，不能增加了。所以，我们的目标是找到从尾到前是减小的数字。

假设数组从尾到前是增加的，然后在有一个地方出现了反转，例如数组：[1，5，8，4，7，6，5，3，1]在7和4的位置出现减小，我们需要做的就是找到该数字，将数字与最接近于并大于该数的数字交换(这里是5)。交换了以后，排列立刻增加了，但是后面的排列仍旧是非常大的。所以应该将之后的数组变成升序排列，也就是将后面的数的排列降到最低。可以分为下面三个步骤：

• 从尾到前，找到反转点
• 从尾部向前找到后半区比该值（1）大的数，交换两个数
• 将后面的数组变成升序排列

也就是说如果对于一个全排列$a_1,a_2,a_3,...,a_k$来说，如果满足$a_1 < a_2 ≥ a_3 ≥ a_4 ... ≥ a_k$（所有$a_1$开头的全排列中字典序最大的情况），就说明这个全排列的下一个全排列不能再由$a_1$开头，而是$a_1$在字典中的下一个元素$a_j$（即满足$a_j > a_1$且$2 ≤ j ≤ k$的最小的$a_j$），由于任何$a_j$开头的全排列都大于$a_1$开头的全排列，所以我们寻找的全排列是$a_j$开头的最小的全排列。

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        # 特殊情况，空的列表或只有一个元素
        if n < 2:
            return


        # 找到从尾到前开始减小的数的下标loc
        loc = None
        for i in reversed(range(1, n)):
            # 找到了
            if  nums[i-1] < nums[i]:
                loc = i-1
                break

        # 始终没有找到，即已经是最大排列，直接反转
        if loc is None:
            nums.reverse()

        else:
            # 找到了该数字，将数字与最接近于并大于该数的数字交换
            larger_than_loc = filter(lambda x: x > nums[loc], nums[loc+1:])
            number_index = nums[loc+1:].index(min(larger_than_loc)) + loc + 1
            nums[number_index], nums[loc] = nums[loc], nums[number_index]
            # 将后面的元素变成升序序列
            nums[loc+1:] = sorted(nums[loc+1:])

参考

• https://shenjie1993.gitbooks.io/leetcode-python/031%20Next%20Permutation.html
• https://www.tianmaying.com/tutorial/LC31
• https://leetcode.com/problems/next-permutation/solution/