Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
You are given an array A of N positive integers. In one move, you can pick a segment (a contiguous fragment) of A and a positive integer X, and then increase all elements within that segment by X.
An array is strictly increasing if each element, except for the last one, is smaller than the next element.
Write a function def solution(A) that, given an array A of N integers, returns the minimum number of moves needed to make the array strictly increasing.
Example 1:
Given A = [4, 2, 4, 1, 3, 5], the function should return 2. One possible solution is to add X = 3 to the segment [2, 4], and then add X = 8 to the segment [1, 3, 5]. As a result of these two moves, A is now strictly increasing.
[4, 2, 4, 1, 3, 5] -> [4, 5, 7, 1, 3, 5] -> [4, 5, 7, 9, 11, 13]Example 2:
Given A = [3, 5, 7, 7], the function should return 1.
Example 3:
Given A = [1, 5, 6, 10], the function should return 0.
这道题其实包含两类常见面试题：括号合法性判断，以及“区间整体加值后让数组严格递增”的贪心 / 差分思路。括号题用栈即可，遇到左括号入栈，遇到右括号就检查栈顶是否匹配，最后栈为空才合法；而数组题的关键是观察相邻元素的关系，若当前元素不大于前一个元素，就必须通过若干次区间加法去“抬高”后缀或某个连续段，使每一步都尽量覆盖更多位置，从而最小化操作次数。示例中 [4,2,4,1,3,5] 需要两次操作，而 [1,5,6,10] 本身已经严格递增，因此答案为 0。
