資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究以 O(1) 時間複雜度和 O(1) 額外空間在 C++ 中查詢棧中的最大值
假設我們想建立一個堆疊，該堆疊可以儲存堆疊中的最大元素。並且我們可以在 O(1) 時間內獲取它。限制條件是，它應該使用 O(1) 額外空間。
我們可以建立一個自定義堆疊，它將儲存最大值，當執行一個操作（例如 pop 或 peek）時，將返回最大值。對於 peek 操作，返回堆疊頂部和最大元素的最大值，對於 pop 操作，當頂部元素較大時，列印它並將最大值更新為 2*max – top_element。否則，返回頂部元素。對於 push 操作，將最大元素更新為 x（要插入的資料），2*x – max。
示例
#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
stack<int> stk;
int stack_max;
public:
void getMax() {
if (stk.empty())
cout << "Stack is empty"<<endl;
else
cout << "Maximum Element in the stack is: "<< stack_max <<endl;
}
void peek() {
if (stk.empty()) {
cout << "Stack is empty ";
return;
}
int top = stk.top(); // Top element.
cout << "Top Most Element is: "<<endl;
(top > stack_max) ? cout << stack_max : cout << top;
}
void pop() {
if (stk.empty()) {
cout << "Stack is empty"<<endl;
return;
}
cout << "Top Most Element Removed: ";
int top = stk.top();
stk.pop();
if (top > stack_max) {
cout << stack_max <<endl;
stack_max = 2 * stack_max - top;
} else
cout << top <<endl;
}
void push(int element) {
if (stk.empty()) {
stack_max = element;
stk.push(element);
cout << "Element Inserted: " << element <<endl;
return;
}
if (element > stack_max) {
stk.push(2 * element - stack_max);
stack_max = element;
} else
stk.push(element);
cout << "Element Inserted: " << element <<endl;
}
};
int main() {
CustomStack stk;
stk.push(4);
stk.push(6);
stk.getMax();
stk.push(8);
stk.push(20);
stk.getMax();
stk.pop();
stk.getMax();
stk.pop();
stk.peek();
}輸出
Element Inserted: 4 Element Inserted: 6 Maximum Element in the stack is: 6 Element Inserted: 8 Element Inserted: 20 Maximum Element in the stack is: 20 Top Most Element Removed: 20 Maximum Element in the stack is: 8 Top Most Element Removed: 8 Top Most Element is: 6
更新於： 2019 年 12 月 18 日
457 次瀏覽
廣告