【hot100-java】【最长递增子序列】

dp篇

一眼单调栈

之前写的python题解 

佬解 单调栈+二分查找

我靠，大师我悟了

class Solution {
    public int lengthOfLIS(int[] nums) {
            if (nums.length<=1){
                return 1;
            }
            List<Integer>stack=new ArrayList<>();
            stack.add(nums[0]);
            for(int i=1;i<nums.length;i++){
                if(nums[i]>stack.get(stack.size()-1)){
                    stack.add(nums[i]);
                }else if(nums[i]<stack.get(stack.size()-1)){
                    int left=0;
                    int right=stack.size()-1;
                    while(left<right){
                        int mid=(left+right)/2;
                        if(nums[i]<=stack.get(mid)){
                            right=mid;
                        }else{
                            left=mid+1;
                        }
                    }
                    stack.set(left,nums[i]);
                }
            }
            return stack.size();
    }
}

ps:

原文地址：https://blog.csdn.net/m0_73629042/article/details/142709859

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！