# 2111. Minimum Operations to Make the Array K-Increasing
###### tags: `Leetcode` `Hard` `Greedy` `Longest Increasing Subsequence`
Link: https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/description/
## 思路
本质就是在每个k间隔的系列里找到最长递增子序列的长度，其余未被选定的元素只需要使之与相邻的元素相同即可, 这样这些未被选中的元素就对应着最少需要修改的数目

**followup**：如果要求构造所有元素为正、且严格的递增序列怎么办？这里会出现的一个问题是，找到LIS之后，其他元素的改动可能无法实现。比如[1,1,2]，最长严格递增序列是[1,2]，但是你无法只修改一个数字得到合法的解。方法是，将所有的元素都减去其下标(1,2,3...)，然后去除掉负数，在其中找LIS（更确切的说是非递减序列）。在这个例子中，变换后的数组是[0,-1,-1]。所以其LIS的长度其实只有1. 去掉负数的那些元素k无论如何都无法成为一个严格递增序列里面的成员，原因是它之前的元素个数太少，即使第一个元素从1开始以公差1递增，到该元素时也超过了k本身。
## Code

class Solution {
    public int kIncreasing(int[] arr, int k) {
        List<Integer> list = new ArrayList<>();
        int ans = 0;
        int n = arr.length;
        for(int i=k; i<2*k; i++){
            int idx = i-k;
            while(idx<n){
                list.add(arr[idx]);
                idx += k;
            }
            ans+=list.size()-LIS(list);
            list = new ArrayList();
        }
        return ans;
    }
    private int LIS(List<Integer> list){
        List<Integer> increasing = new ArrayList<>();
        for(int i=0; i<list.size(); i++){
            int num = list.get(i);
            if(increasing.size()==0 || increasing.get(increasing.size()-1)<=num){
                increasing.add(num);
            }
            else{
                int start = 0, end = increasing.size()-1;
                while(start<end){
                    int mid = start+(end-start)/2;
                    if(increasing.get(mid)<=num){
                        start = mid+1;
                    }
                    else end = mid;
                }
                increasing.set(start, num);
            }
        }
        return increasing.size();
    }
}