这次比赛，网站挂了10多分钟。后来终于进去了。
我做出来3道，最后一道知道是DP，最后一步没当场分析出来。最后排名132/4300
900. RLE Iterator
https://leetcode.com/contest/weekly-contest-101/problems/rle-iterator/
这道题目就是，2个数字为一组，告诉你有几个几。
然后NEXT，就根据翻译出来的数来取。
比如【3,1】就是 【1,1,1】
那么肯定就是维护一个REST变量，和一个指针P，表明遍历到目前为止，指的这个数还剩几个没遍历。
比如上面的例子。我调用next（2） 那就是 P指向1，REST 为1. 还有1和1没用。
int[] A;
int p;
int rest = 0;
public RLEIterator(int[] A) {
this.A = A;
p = -1;
}
public int next(int n) {
while(rest - n < 0){
n -= rest;
p+=2;
if(p>=A.length) return -1;
rest = A[p-1];
}
rest -= n;
if(p>=A.length) return -1;
return A[p];
}
901. Online Stock Span
https://leetcode.com/problems/online-stock-span/description/
这是道要维护前面所有小于等于当前值的题。那么看数据规模还要求O N
果断，知道每一步要么是O 1 要么是 Log N。
因为是维护前面连续的数，所以2分的概率不大。
一旦一个数大于栈顶元素，那么就可以把连续给断开。
比如 60,60,70,60. 最后一个60因为被70阻隔开了，所以只能返回1，而不是3.
根据这个性质。我们可以想到单调栈。如果一个数大于栈顶，其实那些小于这个数就可以POP了，因为也用不到了。
Stack<int[]> st = new Stack<>();
int idx = 0;
public StockSpanner() {
st.push(new int[]{10001,-1});
}
public int next(int price) {
while(st.peek()[0]<=price){
st.pop();
}
int res = idx-st.peek()[1];
st.push(new int[]{price,idx++});
return res;
}
902. Numbers At Most N Given Digit Set
https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
这道题也不是太难。我的解法是先用公式把所有位数比N小的，求掉。
比如1,2,3. 3个数。 N=100，位数为3. 我们先把位数为1，和位数为2的求了。
位数为1的是3. 位数为2的个数是33.
再在位数和N相同的情况下，一位一位求。
位数相同
我们先看第一位能用几个。1，2,3 ； N=200 第一位是2.
我们先把第一位是比2小的数找到K 找到 然后后面2位，就可以随意了。K3^(n-1)
下面看这个2是不是和能用的数相等。试的话，我们接着去求下一位，公式一样。
如果是1,3,5； N=200； 我们发现是3》2； 这个情况就可以直接跳出循环了。
public int atMostNGivenDigitSet(String[] D, int N) {
N++;
int l = D.length;
int nl = (N+"").length();
//cnt digit number < nl
int cnt = 0;
for(int i = 1; i < nl; i++){
cnt += (int)Math.pow(l,i);
}
//cnt digit number = nl
int k = nl-1;
for(char c : (N+"").toCharArray()){
int i = 0;
for(; i < l && D[i].charAt(0) < c ; i++){}
cnt += (i*(Math.pow(l,k)));
if(i<l && D[i].charAt(0) == c){
k--;
}else{
break;
}
}
return cnt;
}
最后我发现，如果正好是每一位都相等，那会漏掉完全相等的这个数。所以一开始用N++。
这样就解决了。
903. Valid Permutations for DI Sequence
https://leetcode.com/problems/valid-permutations-for-di-sequence/description/
这道题的思路是这样的。
我们先从DI来分析。
D 势必为1,0
如果之后是I。我们可以列举以J为结尾的上升时什么。 首先以0为结尾是不可能的。
其次，以1为结尾是可以的201. 以2为结尾也是可以的 是102
我们不妨定义（DP I J） 就是 I个数字的全排列里，符合到PATTERN.substring(0,i-1)的最后一个数字为J的个数有几个。
根据题目的例子
DID 的情况
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
dp[4][0] = 2
dp[4][1] = 2
dp[4][2] = 1
dp[4][3] = 0
dp[4][4] = 0
如果我们要在DID 后面多加一个D，会怎么转变呢
如果要符合条件，dp[5][0] = {(2+1, 1+1, 3+1, 0+1,0)，(2+1, 1+1, 3+1, 0+1,0)}（这里可以得知dp[5][0] = 0+dp[4][0]）
dp[5][0] = {(2+1, 0+1, 3+1, 1+1,0)，(3+1, 0+1, 2+1, 1+1,0)} （这里可以得知dp[5][0] = dp[4][0]+dp[4][1]）
dp[5][0] = {(1, 0+1, 3+1, 2+1,0)} （这里可以得知dp[5][0] =dp[4][0]+dp[4][1]+dp[4][2]）
那么当D的时候，dp[i][j] 可以从 dp[i-1][k] (k from j ... i-1)
同样可以发现dp[i][j] 在最后一个是字母是I的时候，我们可以从dp[i-1][k](k from 0...j-1)
那么比如DIDI的情况
dp[5][0] = 0 因为J-1《0
dp[5][1] = {(2+1, 1+1, 3+1, 0,1),(3+1, 1+1, 2+1, 0,1)} dp[5][1] = dp[4][0]
dp[5][2] = {(2+1, 1, 3+1, 0,2),(3+1, 1, 2+1, 0,2)} + {(2+1, 0, 3+1, 1,2),(2+1, 0, 3+1, 1,2)} dp[5][2] = dp[4][0]+dp[4][1]
综上
public int numPermsDISequence(String s) {
int n = s.length()+1;
long[][] dp = new long[n][n];
dp[0][0] = 1;
int M = 1000000007;
for(int i = 1; i < n; i++){
for(int j = 0; j <= i; j++){
if(s.charAt(i-1) == 'D'){
for(int k = j; k < i; k++)
dp[i][j] = (dp[i][j]+dp[i-1][k])%M;
}else{
for(int k = 0; k < j; k++)
dp[i][j] = (dp[i][j]+dp[i-1][k])%M;
}
}
}
long ans = 0;
for(int i = 0; i < n; i++) ans = (ans+dp[n-1][i])%M;
return (int) ans;
}
下面我们思考可不可以优化，因为我看到最后生成答案有一个累加的操作。我就思考了这么一个问题，我可以不可以让DP状态就表示为（DP I J） 就是 I个数字的全排列里，符合到PATTERN.substring(0,i-1)的最后一个数字至多为J的个数有几个。
这样我最后就可以直接范围DP[N-1][N-1]就是解了。
随后我依然把这个解给摆出来。
DI 的情况有
（2,0,1）dp[3][1] = 1
（1,0,2）dp[3][2] = dp[3][1]+1 = 2;
dp[3][3] = dp[3][2]+0=2;
如果后面接了D
dp[4][0] 当最后一个数是0的话，那么就意味着，之前3,3的所有可能都可以组成新的解。因为只要在3的位置，所有的解，最后补上0，前面+1，都是WORK的。
dp[4][1] ,肯定是包含DP[4][0]的，如果最后一位需要是1. （3,0,2,1）（2,0,3,1）也是可以的
目前还看不出规律。
dp[4][2] = dp[4][1] + 最后一位需要是2的，这时我们会发现 (2,0,1,2) 是没法通过加1，使得最后一位是2，同时保持下降的。
所以我们需要排除dp[3][1]这个解，而这个1，是比当前的2小1 的。
我们猜想公式为dp[i][j] = dp[i][j-1]+dp[i-1][i-1]-dp[i-1][j-1]
这个递推公式的含义就是，少这个位数，如果要让最后一位是J，必须前一位至少也需要是J，所以J-1的都不行。
下面再看I的情况，我们可以得知，最后一位是0，是不可能存在I的。那么DP[4][1]。我们就可以加上DP[3][0]的那些解，最后补上1. 同理DP[4][2] 所有DP[3][1]的解都可以再最后补上2.
我们猜想公式为dp[i][j] = dp[i][j-1]+dp[i-1][j-1]
最后处理下边界情况。得到代码如下，时间复杂度被优化到N ^2
public int numPermsDISequence(String s) {
int l = s.length()+1;
int[][] dp = new int[l][l];
dp[0][0] = 1;
int M = 1000000007;
for(int i = 1; i < l; i++){
for(int j = 0; j <= i; j++){
if(s.charAt(i-1) == 'D'){
if(j!=0){
dp[i][j] = (dp[i][j-1]-dp[i-1][j-1]+M)%M;
}
dp[i][j] = (dp[i][j]+dp[i-1][i-1])%M;
}else{
if(j!=0){
dp[i][j] = (dp[i][j-1]+dp[i-1][j-1])%M;
}
}
}
}
return dp[l-1][l-1];
}
