Solution by special data structure of TreeSet and Stack with getMax() method,but time exceed


  • 0
    D

    I wander why my solution was timelimit exceed,since I implement a special stack to reverse collect the max prices of left part while use a TreeSet to collect the current min price and finally get the difference as the max profit, here the time of construct my stack is just O(n) and get the max value of stack is O(1), while get the min of TreeSet is O(1),and I just traverse the array twice, is it because the construction of TreeSet that exceed the time? here is my code, any advice is appreciated.

        public static int maxProfit(int[] prices) {
        	if(prices==null || prices.length==0){
        		return 0;
        	}
        	//use stack with max to reverse collect the current max prices 
            MaxStack stack=new MaxStack();
            for(int i=prices.length-1;i>0;i--){
            	stack.push(prices[i]);
            }
            TreeSet<Integer> set=new TreeSet<>();
            int maxProfit=0;
            for(int i=0;i<prices.length-1;i++){
            	set.add(prices[i]);
            	int maxLeft=stack.max();
            	stack.pop();
            	int diff=maxLeft-set.first();
            	maxProfit=maxProfit>diff?maxProfit:diff;
            }
            return maxProfit;
        }
    
    class MaxStack{
    	Stack<Integer> stack1=new Stack<>();	//实现栈的常规功能
    	Stack<Integer> stack2=new Stack<>();	//辅助栈,栈顶保存当前最小元素
    	
        public void push(int node) {
            stack1.push(node);
            if(!stack2.isEmpty()){        	
            	stack2.push((max()>=node?max():node));
            }
            else{
            	stack2.push(node);
            }
        }
        
        public void pop() {
            stack1.pop();
            stack2.pop();
        }
        
        public int top() {
            return stack1.peek();
        }
        
        public int max() {
            return stack2.peek();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.