DailyTemperatures [source code]


public class DailyTemperatures {
static
/******************************************************************************/
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // Think carefully about each of the two dimension lengths
        int[][] next = new int[101][temperatures.length];
        for (int i = 0; i < next.length; i++) {
            for (int j = 0; j < next[i].length; j++)
                next[i][j] = -1;
        }
        for (int i = 0; i < temperatures.length; i++) {
            int temp = temperatures[i];
            for (int j = i - 1; j >= 0 && next[temp][j] < 0 ; j--)
                next[temp][j] = i;
        }
        int[] ans = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            int curAns = Integer.MAX_VALUE;
            for (int t = temperatures[i] + 1; t <= 100; t++) {
                if (!(next[t][i] < 0) && next[t][i] < curAns)
                    curAns = next[t][i];
            }
            ans[i] = curAns < temperatures.length ? curAns - i : 0;
        }
        return ans;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        DailyTemperatures.Solution tester = new DailyTemperatures.Solution();
        int[][] inputs = {
            {73,74,75,71,69,72,76,73}, {1,1,4,2,1,1,0,0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] temperatures = inputs[2 * i];
            int[] ans = inputs[2 * i + 1];
            String ansStr = Printer.array (ans);
            System.out.println (Printer.separator ());
            int[] output = tester.dailyTemperatures (temperatures);
            String outputStr = Printer.array (output);
            System.out.printf ("[%s] -> [%s], expected: [%s]\n",
                Printer.array (temperatures), Printer.wrapColor (outputStr, outputStr.equals (ansStr) ? "green" : "red"), ansStr
            );
        }
    }

    static void printNext (int[][] next) {
        for (int i = 0; i < next.length; i++) {
            StringBuilder sb = new StringBuilder ();
            sb.append (String.format ("%3d: ", i));
            boolean can_print = false;
            for (int j = 0; j < next[i].length; j++) {
                // use OR because we want "at least one"
                can_print = can_print || (next[i][j] > 0);
                sb.append (String.format ("%4d ", next[i][j]));
            }
            if (can_print)
                System.out.println (sb.toString ());
            // StringBuilder does not have CLEAR function: use NEW or SET_LENGTH
            sb.setLength (0);
        }
    }
}

看了一下题目, 好像不是特别难, 一个反向查询应该就能搞定, 当然也可能是我猜错了;

刚开始, 我想要: 

        List<Integer>[] tempCounts = new ArrayList<Integer> [101];

但是查了一下这里, 可以看到array of parameterized types是不可以的; 所以这里看来只能用Map了;

这题最后超时了也没有做出来, 当时写的代码是: 

class Solution {  
    public int[] dailyTemperatures(int[] temperatures) {  
        Map<Integer, List<Integer>> tempCounts = new HashMap<> ();  
        int maxTemp = -1;  
        for (int i = 0; i < temperatures.length; i++) {  
            tempCounts.computeIfAbsent (temperatures[i], key -> new ArrayList<> ()).add (i);  
            maxTemp = Math.max (maxTemp, temperatures[i]);  
        }  
        int[] res = new int[temperatures.length];  
        for (int i = 0; i < res.length; i++) {  
            for (int j = temperatures[i] + 1; j <= maxTemp; j++) {  
                if (!tempCounts.containsKey (j))  
                    continue;  
                List<Integer> indices = tempCounts.get (j);  
                if (indices.get (indices.size () - 1) <= i)  
                    continue;  
                int resIndex = -1;  
                for (Integer index : indices) {  
                    if (index > i) {  
                        resIndex = index;  
                        break;  
                    }  
                }  
                if (resIndex > 0) {  
                    res[i] = resIndex - i;  
                    break;  
                }  
            }  
        }  
        return res;  
    }  
}

但是这个代码明显有问题: 

{69=[4], 71=[3], 72=[5], 73=[0, 7], 74=[1], 75=[2], 76=[6]}  
i:(0), temp:(73)  
    temp:(74), positions:[1]  
    found 1 for res[0]  
i:(1), temp:(74)  
    temp:(75), positions:[2]  
    found 2 for res[1]  
i:(2), temp:(75)  
    temp:(76), positions:[6]  
    found 6 for res[2]  
i:(3), temp:(71)  
    temp:(72), positions:[5]  
    found 5 for res[3]  
i:(4), temp:(69)  
    temp:(71), positions:[3]  
    temp:(72), positions:[5]  
    found 5 for res[4]  
i:(5), temp:(72)  
    temp:(73), positions:[0, 7]  
    found 7 for res[5]  
i:(6), temp:(76)  
i:(7), temp:(73)  
    temp:(74), positions:[1]  
    temp:(75), positions:[2]  
    temp:(76), positions:[6]  
[73 74 75 71 69 72 76 73 ] -> [1 1 4 2 1 2 0 0 ], expected: [1 1 4 2 1 1 0 0 ]

而且一个更关键的问题是, 这题明显是希望你做到O(N)的复杂度的, 不然直接一个笨办法做, 无非是站在每一个index, 直接向后扫就行了, 最后也是一个N^2的复杂度; 我上面这个算法, 实际上是做不到O(N)的;

想了一会儿还是放弃了, 完全没有什么想法; 总感觉思路就在嘴边上, 但是就是想不出来;

Editorial

Approach #1: Next Array [Accepted]

Intuition

The problem statement asks us to find the next occurrence of a warmer temperature. Because temperatures can only be in [30, 100], if the temperature right now is say, T[i] = 50, we only need to check for the next occurrence of 51, 52, ..., 100 and take the one that occurs soonest.

Algorithm

Let's process each i in reverse (decreasing order). At each T[i], to know when the next occurrence of say, temperature 100 is, we should just remember the last one we've seen, next[100].

Then, the first occurrence of a warmer value occurs at warmer_index, the minimum of next[T[i]+1], next[T[i]+2], ..., next[100]. 

class Solution {  
    public int[] dailyTemperatures(int[] T) {  
        int[] ans = new int[T.length];  
        int[] next = new int[101];  
        Arrays.fill(next, Integer.MAX_VALUE);  
        for (int i = T.length - 1; i >= 0; --i) {  
            int warmer_index = Integer.MAX_VALUE;  
            for (int t = T[i] + 1; t <= 100; ++t) {  
                if (next[t] < warmer_index)  
                    warmer_index = next[t];  
            }  
            if (warmer_index < Integer.MAX_VALUE)  
                ans[i] = warmer_index - i;  
            next[T[i]] = i;  
        }  
        return ans;  
    }  
}

这个算法总体上来说还是非常聪明的;

在开发自己的算法的过程中, 我首先是意识到了这道题对于反向查询的一个依赖性; 但是比如你站在75的位置, 你可以查询[76, 100]的所有的occurrence, 但是比如对于76, 你怎么找到他的所有的occurrence当中出现在2之后的呢? 当然, 一个可能的思路, 或许是建立一个二维的表, 两个index一个是temp的value, 一个是start index; 这个方法我后面试一下行不行; 不对, 这个方法其实还是有问题: 复杂度太高了. 如果要更新这个二维表, 那么比如你在76这里, ...好像也不是太高; 我后面还是尝试写一下;

至于他这里这个算法, 就真的很聪明; 上面的解释应该是讲的比较清楚了; 这个题目我隐约感觉到确实是一个高阶的historical stream的问题, 这也是为什么我几乎没有思路, 我对这类问题向来不是很有把握;

这题的hint其实讲的很笼统, 一个remember讲的很轻松, 不过这里最后这个remember怎么实现就非常的有讲究;

2sum and repeated lookup

这个题目的history的维护, 跟2sum还是有一定的类似之处的; 首先, 你可能会思考, 这个反向扫, 是怎么想到的? 你首先还是从最naive的笨办法开始思考; 笨办法怎么做, 比如站在2这个位置, 然后把[2:]所有的都扫一遍, 找first larger就行了; 那么我们思考, 笨办法的问题是什么? 复杂度太高, 因为什么? 因为做了很多的重复工作, 如果你从左到右扫, 那么越是右边的value, 被重复扫描的次数越多;

这个问题跟我们在2sum里面碰到的问题是类似的; 比如2sum的笨办法是什么? 站在一个index, 直接向左回头扫, 这个就导致了左边的大量重复; 2sum当时解决这个问题的办法, 就是因为重复在左边, 所以从左到右的顺序扫, 但是对于history用一个更好的方式来维护;

这样的思路也可以放到这一题来用, 这一题我们的重复大量发生在右边, 所以我们完全就可以从右向左扫, 当然, 右边的history怎么维护, 还要另外想办法;

实际上最后循环内部body的组成, 和2sum也是非常类似的; read then write, 这个也算是一个经典的套路了; 总结起来, 每一个iteration的body要完成的, 首先是read, 以完成对当前iteration自己的操作; 然后是关键: 要完成一个additional write/store to history, 这样后面的iteration才能同样快速的read;

Approach #2: Stack [Accepted]

Intuition

Consider trying to find the next warmer occurrence at T[i]. What information (about T[j] for j > i) must we remember?

看看, 他这里的思路就非常的有条理, 站在一个位置, 我们要read什么? 然后后面就是为了保证每个位置有的(快速的)read, 我们在每个位置还要怎么做一个额外的store?

Say we are trying to find T[0]. If we remembered T[10] = 50, knowing T[20] = 50 wouldn't help us, as any T[i] that has its next warmer ocurrence at T[20] would have it at T[10] instead. However, T[20] = 100 would help us, since if T[0] were 80, then T[20] might be its next warmest occurrence, while T[10] couldn't.

Thus, we should remember a list of indices representing a strictly increasing list of temperatures. For example, [10, 20, 30] corresponding to temperatures [50, 80, 100]. When we get a new temperature like T[i] = 90, we will have [5, 30] as our list of indices (corresponding to temperatures [90, 100]). The most basic structure that will satisfy our requirements is a stack, where the top of the stack is the first value in the list, and so on.

Algorithm

As in Approach #1, process indices i in descending order. We'll keep a stack of indices such that T[stack[-1]] < T[stack[-2]] < ..., where stack[-1] is the top of the stack, stack[-2] is second from the top, and so on; and where stack[-1] > stack[-2] > ...; and we will maintain this invariant as we process each temperature.

熟悉这个表达方式, Stack的top应该看成是他的tail/end, 而不是beginning;

After, it is easy to know the next occurrence of a warmer temperature: it's simply the top index in the stack.

Here is a worked example of the contents of the stack as we work through T = [73, 74, 75, 71, 69, 72, 76, 73] in reverse order, at the end of the loop (after we add T[i]). For clarity, stack only contains indices i, but we will write the value of T[i] beside it in brackets, such as 0 (73).

看他这里, 他决定trace的时候用end of the iteration时刻的state, 这个跟我一直用的before each iteration其实是差不多的;

  • When i = 7, stack = [7 (73)]. ans[i] = 0.
  • When i = 6, stack = [6 (76)]. ans[i] = 0.
  • When i = 5, stack = [5 (72), 6 (76)]. ans[i] = 1.
  • When i = 4, stack = [4 (69), 5 (72), 6 (76)]. ans[i] = 1.
  • When i = 3, stack = [3 (71), 5 (72), 6 (76)]. ans[i] = 2.
  • When i = 2, stack = [2 (75), 6 (76)]. ans[i] = 4.
  • When i = 1, stack = [1 (74), 2 (75), 6 (76)]. ans[i] = 1.
  • When i = 0, stack = [0 (73), 1 (74), 2 (75), 6 (76)]. ans[i] = 1. 
class Solution {  
    public int[] dailyTemperatures(int[] T) {  
        int[] ans = new int[T.length];  
        Stack<Integer> stack = new Stack();  
        for (int i = T.length - 1; i >= 0; --i) {  
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();  
            ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;  
            stack.push(i);  
        }  
        return ans;  
    }  
}

这个算法核心上还是跟上面的算法类似的一个历史信息流的算法, 不过用了Stack之后, 不用依赖于domain信息了; 但是有一点不是很理解, 这个Stack到底是怎么定义的? 也就是说, 代表的是什么? awice这里好像并没有明确的说明;

当然算法本身的计算原理还是理解一点的, 比如你可以观察为什么在6的位置的时候, 6(76)可以踢掉7(73)? 这是因为前者的index更小, 然后value反而更大, anything you can do, I can do better. 不过我还是希望能够给这个Stack一个准确的declarative定义, 而不是这里单纯的imperative的一个理解;

想了半天想不通; 如果硬要从declarative的角度上理解这个Stack的作用, 你要站在一个iteration的位置, 思考这个Stack能够向当前这个i提供什么: larger index, ... 我想了一下, 这个Stack的作用其实是简化了我前面想要做的那个二维表的作用: 如果我们从右向左, 那么我们需要维护的始终是larger index的history, 这个也是我的二维表想要提供的功能;
在保证前面这个前提的基础上, 就要考虑这个history Stack本身需要维护哪些信息;

如果真的想要知道这个算法是怎么想出来的, 我想到的一个思路是这样的, 首先, 从右到左的这个顺序是一定要知道的; 然后在我们扫的过程中, 我们只push不pop; then, what do you need to do in each iteration regarding reading the history? 一个直观的思路就是扫一遍, 但是这样最后的复杂度和暴力算法就没有区别了; 然后在这里观察优化空间; 有一些位置的数字是完全不会发挥作用的, 这些要在适当的时候踢掉; 当然, 这个只是一个尝试性的理解, 并不能完整的解释how anyone would come up with such a solution;

另外, 这个的复杂度你会分析吗? 其实是O(N):

Each index gets pushed and popped at most once from the stack.

这句话在分析Stack或者queue之类需要不停维护的数据结构的算法的时候好像经常出现; 虽然我是知道大体上这个属于是aggregate analysis, 不过具体到这个问题上面, 能理解到这一点并不是那么容易;

受到上面的第一种做法的影响, 我自己前面的代码就是根据这个next的做法更改得到的, 不过我没有意识到2sum问题的相似性, 只是用更笨的方法来做; 最后的速度是143ms, 然后editorial2的速度是76ms, editorial1的速度是33ms. 只能说还可以接受吧. 起码我这个做法也是O(N)的;

discussion最优解就是这个Stack的做法, 讲真的, 这个做法真的是很难想到的, next array那个做法好歹我感觉还是人能想出来的, Stack这个做法真的就要观察力相当的敏锐才能看到了;

@luckman said in [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;  
}

下面的评论里面提到一个类似的题目:

@FrancisGee said in [Java] Easy AC Solution with Stack:

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

这个题目我好像并没有做过, 先摆在这里, 看后面能不能有点印象;

还真有人测试了一下, Stack好像真的比较慢;

@luckman said in [Java] Easy AC Solution with Stack:

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

很让我没有想到的是, 这个题目居然真的跟NGE有相似性; 这个是discussion上面一个类似的解法:

@jianchao.li.fighter said in O(n) Java Stack:

This problem is a variant of Next Greater Element I. In that problem, you are required to find the first next greater element while in this problem you are required to find the index difference from the current element to the first next greater element.

Let's put it simple with an example. Suppose temperatures = {60, 59, 61}, in Next Greater Element I, the next greater element for 60 is 61. So you will return 61 for 60. In this problem, you will return the index difference of the next greater element instead: 60 is at index 0 and 61 is at index 2, so you will return 2 - 0 = 2 for 60.

So by modifying the return values of Next Greater Element I, you will get the following solution.

```java

class Solution {
public int[] dailyTemperatures(int[] temperatures) {
final int m = temperatures.length;
final Map next = new HashMap<>();
final Stack stack = new Stack<>();
for (int i = 0; i < m; i++) {
while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
next.put(stack.peek(), i - stack.pop());
}
stack.push(i);
}
final int[] ans = new int[m];
for (int i = 0; i < m; i++) {
ans[i] = next.getOrDefault(i, 0);
}
return ans;
}
} 

>   
> And since we are handling indexes instead of the temperatures, we can further get rid of the Map `next` and put the results in `ans` directly. Thanks to @xpfxzxc for the remind and sharing of his solution.  
>   
```java

class Solution {  
    public int[] dailyTemperatures(int[] temperatures) {  
        final int m = temperatures.length;  
        final int[] ans = new int[m];  
        final Stack<Integer> stack = new Stack<>();  
        for (int i = 0; i < m; i++) {  
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {  
                ans[stack.peek()] = i - stack.pop();  
            }  
            stack.push(i);  
        }  
        return ans;  
    }  
}

Time complexity: O(m) since each of the m indexes of temperatures will be pushed to or popped out of stack for at most once.
Space Complexity: O(m) since stack, next and ans will contain no more than m elements.

其实只要你大胆的理解到了这两个问题的相似性, 这个答案的改法就不算复杂了; 我自己写的时候好像稍微想到了一点这个可能性, 不过并没有具体的落实下来;

反过来想, NGE问题估计也可以用这题见到的这个方法来解? 不过说实话, 这题的editorial2给的这个Stack解法的思考难度确实比NGE问题上面这个Stack解法的难度要高一些; 不过如果还是按照我们之前分析2sum问题的思路, 确实应该是用从右向左的做法更加合适一些, 虽然对应的history的维护也更加复杂一些;

这个题目就基本这几种做法了; 这个题目我认为应该重点多思考一下; 尤其是最好后面把这个题目的做法再给应用到NGE去, 也就是这个DT问题和NGE问题, 你都要分别掌握正序和逆序的做法;

Problem Description

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note:

  • The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Difficulty:Medium
Total Accepted:6.5K
Total Submissions:12.1K
Contributor:Rizve
Companies
google
Related Topics
hash tablestack
Similar Questions
Next Greater Element I

Hint 1
If the temperature is say, 70 today, then in the future a warmer temperature must be either 71, 72, 73, ..., 99, or 100. We could remember when all of them occur next.

results matching ""

    No results matching ""