【面接アルゴリズム問題】O(1)時間複雑度内スタック内最大値を求める
タイトル
pushおよびpop動作を有するスタックstackであり、その時間的複雑さはいずれもO(1)である.アルゴリズムmax操作を設計し,スタック中の最大値を求め,この操作の時間複雑度もO(1)を要求する.スタックの格納方式,push,popの操作は修正できるが,O(1)の時間的複雑度を保証するには,空間的時間的複雑度は要求されない.
私の実現
説明のとても良いブログ:https://blog.csdn.net/taotaotheripper/article/details/8652665 https://blog.csdn.net/sheepmu/article/details/38459165 https://blog.csdn.net/KeepThinking_/article/details/9107697
pushおよびpop動作を有するスタックstackであり、その時間的複雑さはいずれもO(1)である.アルゴリズムmax操作を設計し,スタック中の最大値を求め,この操作の時間複雑度もO(1)を要求する.スタックの格納方式,push,popの操作は修正できるが,O(1)の時間的複雑度を保証するには,空間的時間的複雑度は要求されない.
私の実現
package qiuzhaoprepare;
import java.util.Scanner;
import java.util.Stack;
class MaxValueStack {
static Stack<Integer> stack = new Stack<Integer>();
static Stack<Integer> maxStack = new Stack<Integer>();
public void push(int value) {
if(maxStack.isEmpty() || value>=maxStack.peek())
maxStack.push(value);
else
maxStack.push(maxStack.peek());
stack.push(value);
}
public int pop() {
if(!stack.isEmpty()) {
int temp = stack.pop();
maxStack.pop();
return temp;
}else
System.out.print("Error, stack is already empty!");
return 0;
}
public int max() {
return maxStack.peek();
}
}
public class MaxStack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
MaxValueStack item = new MaxValueStack();
for(int i=0;i<n;i++)
item.push(arr[i]);
int res = item.max();
System.out.print(res);
sc.close();
}
}
その他説明のとても良いブログ:https://blog.csdn.net/taotaotheripper/article/details/8652665 https://blog.csdn.net/sheepmu/article/details/38459165 https://blog.csdn.net/KeepThinking_/article/details/9107697