我有一个列表输入:[70,71,74,69,70,76,71,80,70,65]
代表当天的温度,我应该返回一个列表,该列表指示比今天热的未来几天的数量。如果没有比今天更热的日子,请在列表中添加0。
对于上述输入,预期输出为[1,1,3,1,1,2,1,0,0,0]
要澄清必要的工作:
我们搜索下一个更高温度的位置。如果没有更高的1,则返回零。例如Index0是70。70之后的下一个温度较高(71)。所以我们写一个1。71后面跟着74,所以我们再次写1。 74之后是69和70,它们较低,而76是较高。所以我们写一个3。依此类推...
我能想到的一种方法是使用两个for循环并查找下一个更高的值。
List<Integer> result = new ArrayList<>(Collections.nCopies(size,0));
for(int i = 0; i<list.size();i++){
for(int j=i+1;j<list.size();j++){
if(list.get(i)<list.get(j)){
result.add(i,j-i);
break;
}
}
}
上述方法的时间复杂度为O(n ^ 2)。我想知道还有其他方法可以使时间复杂度更好吗?
最佳答案
我将假设您不是要知道每个元素与下一个严格更大的元素之间的距离,因为这与您的预期输出匹配。
只需使用堆栈,首先将第一个元素推入堆栈,然后从第二个元素开始对数组进行迭代,检查当前元素是否大于堆栈中的顶部元素。如果更大,则当前索引是堆栈顶部元素的答案,更新它的答案并弹出它,然后为堆栈中的新顶部元素重复。重复此操作,直到堆栈为空或当前元素不大于堆栈顶部元素。之后,将当前元素也推入堆栈,以便我们找到它的答案并继续迭代。
此方法的复杂度为O(n)。
这是我在https://www.geeksforgeeks.org/next-greater-element/上找到的代码,为了满足您的确切需求,对其进行了稍微的修改:
//Java program to print next
//greater element using stack
import java.util.ArrayList;
import java.util.Collections;
public class NGE
{
static class stack
{
int top;
int items[] = new int[100];
// Stack functions to be used by printNGE
void push(int x)
{
if (top == 99)
{
System.out.println("Stack full");
}
else
{
items[++top] = x;
}
}
int pop()
{
if (top == -1)
{
System.out.println("Underflow error");
return -1;
}
else
{
int element = items[top];
top--;
return element;
}
}
boolean isEmpty()
{
return (top == -1) ? true : false;
}
}
/* prints element and NGE pair for
all elements of arr[] of size n */
static void printNGE(int arr[], int n)
{
int i = 0;
stack s = new stack();
s.top = -1;
int element, next;
//answer initialized with zeros
ArrayList<Integer> answer = new ArrayList<>(Collections.nCopies(n, 0));
/* push the first element to stack */
s.push(0);
// iterate for rest of the elements
for (i = 1; i < n; i++)
{
next = i;
if (s.isEmpty() == false)
{
// if stack is not empty, then
// pop an element from stack
element = s.pop();
/* If the popped element is smaller than
next, then a) print the pair b) keep
popping while elements are smaller and
stack is not empty */
while (arr[element] < arr[next])
{
answer.set(element, next - element);
if (s.isEmpty() == true)
break;
element = s.pop();
}
/* If element is greater than next, then
push the element back */
if (arr[element] > arr[next])
s.push(element);
}
/* push next to stack so that we can find next
greater for it */
s.push(next);
}
System.out.println(answer);
}
public static void main(String[] args)
{
int arr[] = { 70, 71, 74, 69, 70, 76, 71, 80, 70, 65 };
int n = arr.length;
printNGE(arr, n);
}
}