[Java] Easy AC Solution with Stack


  • 23
    L

    Time: O(N)
    Space: O(N)

    Method 1. Stack (54 ms)

    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++) {
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                ret[idx] = i - idx;
            }
            stack.push(i);
        }
        return ret;
    }
    

    Method 2. Array (10 ms)

    public int[] dailyTemperatures(int[] temperatures) {
        int[] stack = new int[temperatures.length];
        int top = -1;
        int[] ret = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++) {
            while(top > -1 && temperatures[i] > temperatures[stack[top]]) {
                int idx = stack[top--];
                ret[idx] = i - idx;
            }
            stack[++top] = i;
        }
        return ret;
    }
    

  • 0
    S

    I liked your solution. Very simple.


  • 0
    Y

    same idea, python version:

        def dailyTemperatures(self, A):
            """
            :type A: List[int]
            :rtype: List[int]
            """
            n=len(A)
            res=[0 for _ in range(n)]
            q,i=[],0
            while i<n:
                    while q and  q[-1][0]<A[i]:
                        idx=q[-1][1]
                        res[idx]=i-idx
                        q.pop()
                    q.append((A[i],i))
                        
                i+=1
            return res

  • 1
    L

    Thanks for providing the python version. It can be shorter if you remove the following if condition, because it is already checked in the while loop.

    if not q:
        q.append((A[i],i))
    

  • 2
    F

    When I saw the question in this competition, I firstly think about Monotonous stack inspired by Largest Rectangle in Histogram.
    Because Monotonous stack can help us find first largest element in O(n) time complexity.
    But I can't implement use Monotonous stack idea to solve the problem.But you did it, brilliant bro.

    According to Java doc
    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

    Use

    Deque<Integer> stack = new ArrayDeque<>();
    

    Maybe better


  • 0
    L

    @FrancisGee Thanks for providing such useful information to us.


  • 1

    @yeyumujiang

    def dailyTemperatures(self, A):
        res = [0] * len(A)
        q = []
        for i, t in enumerate(A):
            while q and t > A[q[-1]]:
                j = q.pop()
                res[j] = i - j
            q.append(i)
        return res

  • 1
    S

    Same wiith leetcode 496. Next Greater Element I, C++ version:

    class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& t) {
            if(t.size()==1) return {0};
            vector<int> retVec(t.size(),0);
            stack<int> mStack;
            for(int i = 0;i<t.size();++i) {
                while(!mStack.empty()&&t[mStack.top()]<t[i]) {
                    retVec[mStack.top()] = i-mStack.top();
                    mStack.pop();
                }
                mStack.push(i);
            }
            return retVec;
            
        }
    };
    

  • 0
    S

    The logic of my solution is same but implementation slightly different. Basically I think for such a problem, reading the array from right to left is more intuitive and easier to understand. Here's the code:

        public int[] dailyTemperatures(int[] temperatures) {
            int n = temperatures.length;
            int[] warmTemperatures = new int[n]; // => each element = 0
            Deque<Integer> ngeStack = new ArrayDeque<>();
            for (int i=n-1; i>=0; i--) {
                while (!ngeStack.isEmpty()) { // search till the stack is empty
                    int topIndex = ngeStack.peek();
                    if (temperatures[i] < temperatures[topIndex]) {
                        warmTemperatures[i] = (topIndex-i);
                        break;
                    } else {
                        ngeStack.pop();
                    }
                }
                ngeStack.push(i);
            }
            return warmTemperatures;
        }
    

  • 0

    @luckman Decreasing stack (单调栈)


  • 0
    L

    @FLAGbigoffer Exactly!


  • 0
    B

    Ruby version same idea...

    # @param {Integer[]} temperatures
    # @return {Integer[]}
    def daily_temperatures(temperatures)
        stack = []
        results = Array.new(temperatures.length, 0)
        temperatures.each_with_index do |temp, i|
            while !stack.empty? && stack.last[:temp] < temp do            
                index = stack.last[:idx]
                results[index] = i - index
                stack.pop
            end
            stack << {"temp": temp, "idx": i}
        end  
        results
    end
    

  • 0
    R

    @luckman Why is Method2 faster ?


  • 0
    L

    @rohit104 I think it is because there would be no resizing by using array. Moreover, reminded by @FrancisGee, Stack is one of the legacy classes in Java and its efficiency is quite low.

    The following is the runtime of using different data structure:
    Stack(54 ms)
    ArrayDeque(33ms)
    Array(10ms)


  • 0
    R

    @luckman Thank you for the response. Also noticed the following in JavaDocs:

    Stack (https://docs.oracle.com/javase/7/docs/api/java/util/Vector.html):
    the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.


  • 1
    M

    @stackoverflow_yang Thanks for providing the C++ version,it seems like this method can be used in Largest Rectangle in Histogram just like @FrancisGee said.


Log in to reply
 

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