前言

• 分割字符串的最大得分
• 可獲得的最大點(diǎn)數(shù)
• 對(duì)角線遍歷II
• 帶限制的字序列和

分割字符串的最大得分

• 題目連接
• 解釋：
  要求我們將所給字符串分成左右兩段，使得左段中0的數(shù)目加上右段中1的數(shù)目之和盡可能的大。
• 解題思路
  首先統(tǒng)計(jì)字符串中0的數(shù)目和1的數(shù)目,然后遍歷字符串，計(jì)算在i位置上時(shí)， [0,i]中0的數(shù)目和[i+1, n)中1的數(shù)目總和，計(jì)算公式如下

• 其中score為在i位置進(jìn)行分割時(shí)的得分，zero表示到i位置時(shí)0的數(shù)目，one表示整個(gè)字符串中1的數(shù)目。

• 代碼

class Solution {
    public int maxScore(String s) {
        int one = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') one++;
        }
        int zero = 0, ans = 0;
        int n = s.length();
        
        // 注意左右兩段均不能為空
        for (int i = 0; i < n-1; i++) {
            if (s.charAt(i) == '0') zero++;
            int cur = zero + one-(i+1-zero);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

• 復(fù)雜度分析：
  時(shí)間復(fù)雜度: 遍歷一遍字符串的開銷，每次計(jì)算時(shí)間復(fù)雜度
  空間復(fù)雜度: 未使用額外空間

可獲得的最大點(diǎn)數(shù)

• 題目鏈接
• 解釋：
  每次從一個(gè)數(shù)組的頭部或尾部取出一個(gè)數(shù)字，最多可取k次，求所取數(shù)字和的最大值。
• 解題思路：
  因?yàn)槊看沃荒軓脑摂?shù)組的頭部或尾部取一個(gè)數(shù)字，因此最終會(huì)剩余一個(gè)長(zhǎng)度為n-k的連續(xù)子數(shù)組(n為)，要想所取數(shù)字和盡可能大，則剩余的子數(shù)組和則需要盡可能小，因此題目轉(zhuǎn)化為求一個(gè)長(zhǎng)度為n-k的連續(xù)子數(shù)組的最小值，為此我們可以簡(jiǎn)單枚舉所有長(zhǎng)度為n-k區(qū)間，而每個(gè)區(qū)間和由可以利用前綴和數(shù)組簡(jiǎn)單的計(jì)算出。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int[] sum = new int[n+1];
        
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + cardPoints[i-1];
        }
        
        int minv = Integer.MAX_VALUE;
        for (int i = 0; i <= n-(n-k); i++) {
            minv = Math.min(minv, sum[i+n-k]-sum[i]);
        }
        return sum[n]-minv;
    }
}

• 復(fù)雜度分析
• 時(shí)間復(fù)雜度:
• 空間復(fù)雜度: ，記錄前綴和數(shù)組所占用的空間。

對(duì)角線遍歷II

• 題目鏈接

• 解釋：
  按照如下的次序遍歷該二維矩陣中的元素

  
  
  遍歷規(guī)則

注意到該矩陣沒行元素?cái)?shù)量不一，最多行列，但是最多只有10^5個(gè)元素，因此我們必須只能遍歷存在的元素，并為每個(gè)元素確定它所在結(jié)果數(shù)組中的具體位置。根據(jù)觀察易發(fā)現(xiàn)如下規(guī)律

1. 在同一斜對(duì)角線上的元素，其所在行x與所在列y之和相同
2. 在同一斜對(duì)角線上的元素，按照所在行x由大到小排序
   基于上述兩點(diǎn)，我們可以先遍歷該不規(guī)則二維矩陣，統(tǒng)計(jì)每個(gè)數(shù)字的所在行x和所在列y，再按照上述規(guī)則排序即可。

• 代碼

class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int n = nums.size();
        List<Point> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int j = nums.get(i).size();
            for (int t = 0; t < j; t++) {
                arr.add(new Point(i, t, nums.get(i).get(t)));
            }
        }
        Collections.sort(arr, (o1,o2)->((o1.x+o1.y)==(o2.x+o2.y)?(o2.x-o1.x):((o1.x+o1.y)-(o2.x+o2.y))));
        int[] ans = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++)
            ans[i] = arr.get(i).val;
        return ans;
    }
}
class Point {
    int x,  y, val;
    public Point(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

• 算法復(fù)雜度
  時(shí)間復(fù)雜度: 其中為二維矩陣中元素個(gè)數(shù)，開銷來自于排序操作。
  空間復(fù)雜度： 其中為二維矩陣中元素個(gè)數(shù)。

帶限制的子序列和

• 題目鏈接

• 解釋：
  題目要求我們找出一個(gè)和最大的子序列，且子序列中任意2個(gè)相鄰元素在原數(shù)組中的位置距離不超過k。

• 分析：
  動(dòng)態(tài)規(guī)劃的方法

1. 設(shè)為以位置為結(jié)束并包含了nums[i]這個(gè)元素的滿足條件的子序列最大和。
2. 則易得動(dòng)態(tài)轉(zhuǎn)移方程為：

根據(jù)以上兩點(diǎn)我們可以容易的實(shí)現(xiàn)一個(gè)時(shí)間復(fù)雜度為的解法，其中為數(shù)組中元素總數(shù)，考慮到和的取值上限均到達(dá)了，該方法會(huì)超時(shí)。

• 優(yōu)化
  根據(jù)動(dòng)態(tài)轉(zhuǎn)移方程可以發(fā)現(xiàn)，為了計(jì)算出，我們僅需要知道到中的最大值，當(dāng)計(jì)算完成后，不再需要，成為了一個(gè)新的需要考慮的元素，也就是說我們要在數(shù)組上維護(hù)一個(gè)大小為的窗口，并在窗口前移的過程中更新窗口中的最大值。為了使得獲取窗口中最大值的速度盡可能快，我們可以用一個(gè)雙端隊(duì)列來維護(hù)更新操作

1. 隊(duì)列的隊(duì)首為當(dāng)前窗口中的最大值
2. 當(dāng)前窗口中的元素?cái)?shù)量到達(dá)k時(shí)，再加入新元素前，要移除一個(gè)最早加入的元素，也就是，若與當(dāng)前隊(duì)首元素相同，則移除隊(duì)首元素，否則說明此時(shí)并不在窗口中（即在下面的插入操作中被淘汰掉），則不做任何操作
3. 把新計(jì)算出的加入到窗口中去，具體操作是和隊(duì)尾元素比較，若比當(dāng)前隊(duì)尾元素大，則把當(dāng)前隊(duì)尾元素淘汰掉，否則將加入到隊(duì)尾。

• 代碼

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length, ans = Integer.MIN_VALUE;;
        int[] dp = new int[n];
        
        LinkedList<Integer> que = new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            int maxv = Math.max(0,que.peekFirst()==null?0:que.peekFirst());
            dp[i] = nums[i] + maxv;
            if (i >= k && que.peekFirst()==dp[i-k]) que.pollFirst();
            while (!que.isEmpty() && dp[i] > que.peekLast()) que.pollLast();
            que.addLast(dp[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

• 復(fù)雜度分析
  時(shí)間復(fù)雜度：
  空間復(fù)雜度：