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.
This set combines two classic interview patterns: stack-based bracket validation and a greedy/difference-style approach for making an array strictly increasing with segment increments. For the bracket problem, use a stack to match opening and closing symbols in order. For the array problem, examine adjacent values and decide when a segment increment is needed to fix a non-increasing break while covering as much of the suffix as possible, so the number of moves stays minimal. The examples show both the transformation process and the case where no moves are needed.
