1562. Find Latest Group of Size M

Link

Solution

跟LCS有點類似。

設計length去紀錄每輪index被set之後，所造成的group長度，並記錄在length[groupStart] ,length[groupEnd]

假設index被set，那所造成的groupLength

groupLength = length[index+1] + length[index-1] + 1;

並更新groupLength到two end，藉此可以一直tracking group變化。

當目標groupLen 被消失時，前一輪就是答案。

  public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if(n == m) return n;
        int res = -1;
        int[] length = new int[n+2]; // update the edge of group to the group length
        //bit [00110000] -> length [0002200000]
        //bit [00111110] -> length [0005???500]
        for(int i = 0; i < n; i++){
            int index = arr[i];
            int leftGrpLen = length[index-1];
            int rightGrpLen = length[index+1];
            length[index-leftGrpLen] = length[index+rightGrpLen] = leftGrpLen + rightGrpLen + 1;
            if(leftGrpLen == m || rightGrpLen == m){
                res = i;
            }
        }
        return res;
    }