# [Java] Easy AC Solution with Stack

• 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;
}
``````

• I liked your solution. Very simple.

• 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``````

• 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))
``````

• 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

• @FrancisGee Thanks for providing such useful information to us.

• @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``````

• 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;

}
};
``````

• 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;
}
``````

• @luckman Decreasing stack (单调栈）

• @FLAGbigoffer Exactly!

• 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
``````

• @luckman Why is Method2 faster ?

• @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)

• @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.`

• @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.

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