题目

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

1
2
3
4
5

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

1
2
3

输入：arr = [11,81,94,43,3]
输出：444

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

思路

用一个栈保存到达i位置时左侧更小值的位置。

dp：以arr[i]为结尾的所有数组的最小值之和。

dp[i+1] = (dp[s.top()+1]+(i-s.top())*arr[i])

dp[s.top()+1]表示s.top()以及之前的所有数组，其数组最小值都是比arr[i]小的，所以前面的延伸到当前arr[i]，最小值不变，其和不变。

(i-s.top())*arr[i]表示以arr[i]为结尾并且以arr[i]为最小值的数组的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int* dp = new int[arr.size()+1];
        int* stack = new int[arr.size()+1];
        memset(dp,0,sizeof(int)*(arr.size()+1));
        memset(stack,0,sizeof(int)*(arr.size()+1));
        int top=-1;
        int mod = 1000000007;
        stack[++top]=-1;
        for(int i=0;i<arr.size();++i){
            while(top>0&&arr[i]<=arr[stack[top]]) top--;
            dp[i+1] = (dp[stack[top]+1]+(i-stack[top])*arr[i])%mod;
            stack[++top]=i;
        }
        int res = 0;
        for(int i=0;i<=arr.size();++i){
            res=(res + dp[i])%mod;
        }
        return res;
    }
};

题目

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: “()”
输出: True

示例 2:

输入: “(*)”
输出: True

示例 3:

输入: “(*))”
输出: True

注意:

1. 字符串大小将在 [1，100] 范围内。

   思路

   主要是(和*的问题。
   总体思路：(和*分别按照相同和相对来看，最后比较记录的(与*相同与不同时的数量即可。
   可以用栈，也可以直接记录，毕竟栈在这里的用途也是记录(和*的数量的。
   lo记录(与*不同时的数量，hi记录(和*相同时的数量。因此当hi<0的时候一定不行（有括号大于做括号和*之和）
   整个遍历结束后，hi肯定是要>=0的，这个时候只需要看lo就可以了，如果lo<=0，那么说明(的数量小鱼等于*的数量，*经过变换可以抵消所有的(。

   代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   class Solution { public: bool checkValidString(string s) { int lo = 0, hi = 0; for(char c:s){ if(c=='('){ lo++; hi++; }else if(c==')'){ lo = max(0,lo-1); hi--; if(hi<0) return false; }else{ lo = max(0,lo-1); hi++; } } return lo<=0; } };