给定一个整数数组 tempratures ，表示第 i 天的温度，请你找出下一个大于第 i 天温度的天数距离第 i 天的差值，输出相差的天数；若无大于第 i 天温度的日子，输出0.

这个问题可以使用单调栈来求解。我们维护一个单调递减的栈，栈中存储的是数组的下标。遍历数组，对于每个元素，如果它比栈顶元素对应的温度高，那么栈顶元素对应的答案就是当前元素的下标减去栈顶元素的下标。我们不断弹出栈顶元素，直到栈为空或者栈顶元素对应的温度大于当前元素的温度。然后把当前元素的下标入栈。最后，如果栈中还有元素，说明它们没有找到下一个更高温度的日子，对应的答案就是0。

以下是实现代码：

def dailyTemperatures(temperatures):
    n = len(temperatures)
    ans = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

时间复杂度为 O(n)，空间复杂度为 O(n)。

相关问题

题目描述 给定一个整数数组 tempratures ，表示第 i 天的温度，请你找出下一个大于第 i 天温度的天数距离第 i 天的差值，输出相差的天数；若无大于第 i 天温度的日子，输出0. 输入输出格式 输入格式 第一行有一个整数 tempraturesSize，表示数组 tempratures 的大小； 第二行有 tempraturesSize 个整数，表示数组 tempratures 的所有元素，每个整数用一个空格隔开。 输出格式 输出 tempratures 中每天对应升温的天数。说明提示 -1≤tempraturesSize≤10 5。C语言

以下是一种基于栈的解法：

#include <stdio.h>
#include <stdlib.h>

struct StackNode {
    int index;
    struct StackNode *next;
};

struct Stack {
    struct StackNode *top;
};

void push(struct Stack *stack, int index) {
    struct StackNode *node = (struct StackNode *)malloc(sizeof(struct StackNode));
    node->index = index;
    node->next = stack->top;
    stack->top = node;
}

int pop(struct Stack *stack) {
    if (stack->top == NULL) {
        return -1;
    }
    struct StackNode *node = stack->top;
    stack->top = node->next;
    int index = node->index;
    free(node);
    return index;
}

int peek(struct Stack *stack) {
    if (stack->top == NULL) {
        return -1;
    }
    return stack->top->index;
}

int *dailyTemperatures(int *temperatures, int temperaturesSize, int *returnSize) {
    int *ans = (int *)malloc(sizeof(int) * temperaturesSize);
    *returnSize = temperaturesSize;
    struct Stack stack = {NULL};

    for (int i = 0; i < temperaturesSize; i++) {
        while (stack.top != NULL && temperatures[i] > temperatures[peek(&stack)]) {
            int index = pop(&stack);
            ans[index] = i - index;
        }
        push(&stack, i);
    }

    while (stack.top != NULL) {
        int index = pop(&stack);
        ans[index] = 0;
    }

    return ans;
}

int main() {
    int temperaturesSize;
    scanf("%d", &temperaturesSize);

    int *temperatures = (int *)malloc(sizeof(int) * temperaturesSize);
    for (int i = 0; i < temperaturesSize; i++) {
        scanf("%d", &temperatures[i]);
    }

    int returnSize;
    int *ans = dailyTemperatures(temperatures, temperaturesSize, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        printf("%d ", ans[i]);
    }
    printf("\n");

    free(temperatures);
    free(ans);

    return 0;
}

该算法的时间复杂度为 O(n)，其中 n 为数组长度。