# 81 new solution

[1nfo]

public class Solution {
    public boolean search(int[] nums, int target) {
        return rbs(nums,0,nums.length,target);
    }

    boolean rbs(int[] nums, int start, int end, int target){
        //System.out.println(start+":"+end);
        if(start==end) return false;
        if(end-start==1) return nums[start]==target;
        if(nums[start]<nums[end-1]) return bs(nums,start,end,target);
        int m = start+(end-start)/2;
        if(nums[m]==target||target==nums[start]||target==nums[end-1]) return true;
        if(end-start==2) return false;
        if(nums[start]==nums[nums.length-1]){
            if(nums[m]==nums[start]) return rbs(nums,start+1,m,target)||rbs(nums,m+1,end-1,target);
            if(nums[m]>nums[start]){
                if(target<nums[start]||target>nums[m]) return rbs(nums,m+1,end-1,target);
                return bs(nums,start+1,m,target);
            }
            else{
                if(target<nums[m]||target>nums[end-1]) return rbs(nums,start+1,m,target);
                return bs(nums,m+1,end-1,target);
            }
        }
        else{
            if(nums[m]>=nums[start]){
                if(target<nums[start]||target>nums[m]) return rbs(nums,m+1,end-1,target);
                return bs(nums,start+1,m,target);
            }
            else{
                if(target<nums[m]||target>nums[end-1]) return rbs(nums,start+1,m,target);
                return bs(nums,m+1,end-1,target);
            }
        }
    }

    boolean bs(int[] nums,int start, int end, int target){
        if(start==end) return false;
        int m = start+(end-start)/2;
        if (nums[m]==target) return true;
        if (nums[m]<target) return bs(nums,m+1,end,target);
        return bs(nums,start,m,target);
    }
}

[1nfo]

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode ret = new ListNode(0), curr=head, prev=ret;
        ret.next = head;
        while(curr!=null&&curr.next!=null){
            while(curr.next!=null&&curr.next.val!=curr.val) {
                prev=curr;
                curr=curr.next;
            }
            if(curr.next==null) return ret.next;
            while(curr.next!=null&&curr.next.val==curr.val) curr=curr.next;
            prev.next=curr.next;
            curr = curr.next;
        }
        return ret.next;
    }
}

[1nfo]

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return head;
        ListNode ret = new ListNode(head.val-1), prev = ret, curr = head;
        ret.next = head;
        while(curr!=null){
            while(curr!=null&&curr.val!=prev.val){
                prev = curr;
                curr = curr.next;
            }
            if(curr==null) break;
            while(curr!=null&&prev.val==curr.val) curr = curr.next;
            prev.next = curr;
        }
        return ret.next;
    }
}

[1nfo]

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        stack.push(-1);
        for(int i=0;i<=heights.length;i++){
            int h = i==heights.length?0:heights[i];
            while(stack.peek()>-1&&heights[stack.peek()]>h){
                max = Math.max(heights[stack.pop()]*(i-stack.peek()-1),max);
            }
            if(i>heights.length-2||heights[i]!=heights[i+1]) stack.push(i);
        }
        return max;
    }
}

using array as stack

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length+2];
        int max = 0, p = -1;
        stack[++p] = -1;
        for(int i=0;i<=heights.length;i++){
            int h = i==heights.length?0:heights[i];
            while(p>0&&heights[stack[p]]>h){
                max = Math.max(heights[stack[p--]]*(i-stack[p]-1),max);
            }
            if(i>heights.length-2||heights[i]!=heights[i+1]) stack[++p]=i;
        }
        return max;
    }
}