အခန်း ၅ - Stack

Stack ဆိုတာ Data တွေကို အထပ်လိုက် စီထားတဲ့ ပုံစံမျိုး (ဥပမာ - စာအုပ်ပုံ) အလုပ်လုပ်တဲ့ Data Structure တစ်ခု ဖြစ်ပါတယ်။ သူ့မှာ အဓိက စည်းကမ်းတစ်ခု ရှိပါတယ်။ အဲ့ဒါကတော့ LIFO (Last-In, First-Out) ဖြစ်ပါတယ်။

LIFO (Last-In, First-Out)

LIFO ဆိုတာ "နောက်ဆုံးမှ ဝင်လာတဲ့ကောင်က ပထမဆုံး ပြန်ထွက်ရမယ်" လို့ ဆိုလိုတာပါ။

လွယ်ကူသော ဥပမာ (Buffet Plates Analogy):
စားသောက်ဆိုင် (Buffet) တစ်ခုမှာ ပန်းကန်ပြားတွေကို ပုံးထဲမှာ တစ်ချပ်ပေါ် တစ်ချပ် ထပ်ပြီး စီထားတာကို မြင်ဖူးမှာပါ။ စားပွဲထိုးက ဆေးပြီးသား ပန်းကန်အသစ်တွေကို ထည့်တဲ့အခါ အပေါ်ဆုံးကနေပဲ ထပ်တင်ရပါတယ်။ (Push)
စားမယ့်သူတွေ လာယူတဲ့အခါကျရင်လည်း အပေါ်ဆုံးက ပန်းကန် (နောက်ဆုံးမှ ဆေးပြီး တင်လိုက်တဲ့ ပန်းကန်) ကိုပဲ အရင်ဆုံး ယူသုံးကြပါတယ်။ (Pop)
အောက်ဆုံး ဆုံးမှာရှိတဲ့ ပန်းကန်ကို လိုချင်ရင် အပေါ်က ပန်းကန်တွေ အကုန်လုံးကို အရင် ဖယ်ထုတ်ပစ်မှသာ ရပါလိမ့်မယ်။ ဒါဟာ LIFO ရဲ့ အကောင်းဆုံး ဥပမာပါပဲ။

အဓိက လုပ်ဆောင်ချက်များ (Operations)

Stack တစ်ခုမှာ အဓိက လုပ်ဆောင်ချက် ၃ ခု ရှိပါတယ် —

Push: Data တစ်ခုကို Stack ရဲ့ အပေါ်ဆုံး (Top) မှာ ထည့်တာ။
Pop: Stack ရဲ့ အပေါ်ဆုံးက Data ကို ဖယ်ရှားပြီး ပြန်ထုတ်ပေးတာ။
Peek / Top: အပေါ်ဆုံးမှာ ဘာရှိလဲဆိုတာကို Data မထုတ်ဘဲ ကြည့်တာ။

ဒီအလုပ် ၃ ခုလုံးဟာ Stack ရဲ့ အပေါ်ဆုံး (Top) မှာပဲ တိုက်ရိုက် လုပ်တာ ဖြစ်တဲ့အတွက် Time Complexity ဟာ $O(1)$ ဖြစ်ပါတယ်။

graph TD
    subgraph "Stack Structure"
    D[Item 4 - Top]
    C[Item 3]
    B[Item 2]
    A[Item 1 - Bottom]
    end
    
    PushIn((Push)) --> D
    D --> PopOut((Pop))
    
    style D fill:#f9f,stroke:#333

Java ဖြင့် Stack အသုံးပြုခြင်း

Java မှာဆိုရင် java.util.Stack ကို သုံးပြီး အလွယ်တကူ ရေးနိုင်ပါတယ်။ (နောက်ပိုင်း ခေတ်သစ် Java မှာ Stack အစား Deque (ဥပမာ ArrayDeque) ကို Stack အနေနဲ့ သုံးဖို့ ပိုမို အကြံပြုကြပါတယ်။ ဒါပေမယ့် Concept ကို နားလည်ဖို့အတွက် ရိုးရှင်းတဲ့ Stack ကို အရင် ကြည့်ရအောင်)။

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack တစ်ခု တည်ဆောက်ခြင်း
        Stack<String> history = new Stack<>();
        
        // Data ထည့်ခြင်း (Push) - O(1)
        history.push("google.com");
        history.push("facebook.com");
        history.push("youtube.com");
        
        // အပေါ်ဆုံးက ဘာလဲ ကြည့်ခြင်း (Peek) - O(1)
        System.out.println("Top Website: " + history.peek()); // youtube.com
        
        // Data ထုတ်ခြင်း (Pop) - O(1)
        String lastVisited = history.pop();
        System.out.println("Back from: " + lastVisited);
        
        // လက်ရှိ အပေါ်ဆုံးက ဘာလဲ
        System.out.println("Now Top is: " + history.peek()); // facebook.com
    }
}

Time Complexity

Operation	Average Case	Worst Case
push	$O(1)$	$O(1)$
pop	$O(1)$	$O(1)$
peek / top	$O(1)$	$O(1)$
search	$O(n)$	$O(n)$

မှတ်ချက်: Stack မှာ Data ရှာဖွေတာ (Search) က $O(n)$ ကြာပါတယ်။ ဘာကြောင့်လဲဆိုတော့ အောက်ဆုံးက Data ကို လိုချင်ရင် အပေါ်က Data တွေကို တစ်ခုချင်းစီ ဖယ်ပြီးမှ ရှာလို့ ရလို့ပါ။ Data ကို လျင်မြန်စွာ ရှာဖွေချင်တယ် ဆိုရင် Hash Table လိုမျိုး အခြား Data Structure တွေကို သုံးရပါမယ်။

လက်တွေ့အသုံးချမှုများ

နေ့စဉ်သုံးနေတဲ့ Software တွေမှာ Stack ကို နေရာများစွာမှာ အသုံးပြုကြပါတယ် —

Undo / Redo Function: စာရိုက်တဲ့အခါ မှားလို့ နောက်ပြန်ဆုတ် (Ctrl+Z) ချင်ရင် နောက်ဆုံးရိုက်ခဲ့တဲ့ အခြေအနေတွေကို Stack ထဲကနေ တစ်ခုချင်း ပြန်ထုတ်ပေးတာပါ။
Browser History (Back / Forward Button): Back Button နှိပ်ရင် နောက်ဆုံးကြည့်ခဲ့တဲ့ Website (Top of Stack) ကို ပြန်ပြတာပါ။
Call Stack: Programming Language အများစုမှာ Function (Method) တစ်ခုထဲကနေ နောက်တစ်ခုကို ထပ်ဆင့်ခေါ်တဲ့အခါ ဘယ်နေရာကနေ ပြန်စရမလဲဆိုတာ မှတ်သားဖို့ Stack Memory ကို သုံးပါတယ်။

Questions

Stack ကို နားလည်သွားပြီ ဆိုရင် Stack ကို လက်တွေ့ အသုံးချရမယ့် LeetCode ပုစ္ဆာ တချို့ကို ကြည့်ရအောင်။

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

ဒီပုစ္ဆာက Stack ကို လေ့လာတဲ့ သူတွေအတွက် အခြေခံ အကျဆုံးနဲ့ အရေးအကြီးဆုံး ပုစ္ဆာ ဖြစ်ပါတယ်။ ကျွန်တော်တို့ string ထဲမှာ အဖွင့် ကွင်း (, {, [ တွေ့တိုင်း Stack ထဲကို push ထည့်ပါမယ်။ အပိတ် ကွင်း တွေ့တဲ့ အခါမှာတော့ Stack ရဲ့ အပေါ်ဆုံးက ကွင်းကို pop လုပ်ပြီး ကိုက်ညီမှု ရှိမရှိ စစ်ဆေးပါမယ်။

$O(n)$ time complexity, space complexity ဖြစ်ရပါမယ်။

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            // အဖွင့်ကွင်းများ ဖြစ်လျှင် သက်ဆိုင်ရာ အပိတ်ကွင်းကို Stack ထဲ ထည့်သည်
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                // အပိတ်ကွင်း ဖြစ်ပါက Stack အလွတ်ဖြစ်နေသလား သို့မဟုတ် 
                // Stack အပေါ်ဆုံးက ကွင်းနှင့် မတူဘူးလား စစ်ဆေးသည်
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }
        
        // Stack လွတ်သွားမှသာ ကွင်းတွေ အစုံအလင် ပိတ်ပြီးသွားတာဖြစ်သည်
        return stack.isEmpty();
    }
}

Swift code နဲ့ ဆိုရင် အခုလို ရေးလို့ ရပါတယ်။ Array ကို လွယ်လွယ်ကူကူ Stack အဖြစ် အသုံးချနိုင်ပါတယ်။

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack = [Character]()
        
        for char in s {
            switch char {
            case "(":
                stack.append(")")
            case "{":
                stack.append("}")
            case "[":
                stack.append("]")
            default:
                if stack.isEmpty || stack.removeLast() != char {
                    return false
                }
            }
        }
        
        return stack.isEmpty
    }
}

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with $O(1)$ time complexity for each function.

Example 1:

Input: ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]

Output: [null,null,null,null,0,null,2,1]

Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top();    // return 2
minStack.getMin(); // return 1

ပုံမှန် Stack မှာ အသေးဆုံး တန်ဖိုး (Minimum element) ကို လိုချင်ရင် အပေါ်ဆုံးကနေ အောက်ခြေ အထိ လိုက်ရှာရတဲ့အတွက် $O(n)$ အချိန် ကြာပါတယ်။ အခုက Pushing နဲ့ Popping လုပ်နေချိန်မှာပါ $O(1)$ Time Complexity နဲ့ အသေးဆုံး တန်ဖိုးကို ချက်ချင်း သိချင်တာပါ။

ဒီ ပြဿနာကို ဖြေရှင်းဖို့အတွက် Stack နှစ်ခု (သို့မဟုတ် Stack တစ်ခုတည်းမှာ Minimum Value ကိုပါ တွဲသိမ်းတာ) သုံးလို့ ရပါတယ်။ minStack ဆိုတဲ့ နောက်ထပ် Stack တစ်ခု ထားပြီး၊ အသစ်ဝင်လာတဲ့ val က လက်ရှိ အသေးဆုံး တန်ဖိုးထက် ငယ်နေရင် (သို့မဟုတ် ညီနေရင်) minStack ထဲကိုပါ ထည့်သိမ်းပေးလိုက်ယုံပါပဲ။

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        // minStack လွတ်နေလျှင် (သို့) ထည့်မည့်တန်ဖိုးသည် လက်ရှိ အနည်းဆုံးထက် ငယ်/ညီ နေလျှင်
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        // ထုတ်လိုက်သော တန်ဖိုးသည် အနည်းဆုံး တန်ဖိုးဖြစ်နေပါက minStack မှပါ ထုတ်သည်
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Reverse Polish Notation (RPN) ဟာ ဂဏန်း (Operands) တွေကို အရင်ရေးပြီးမှ ပေါင်းနှုတ်မြှောက်စား သင်္ကေတ (Operators) တွေကို နောက်ကနေ ကပ်ရေးတဲ့ နည်းစနစ်ပါ။ ဥပမာ 2 + 1 ကို RPN နဲ့ ရေးရင် 2 1 + ဖြစ်ပါတယ်။ RPN ဟာ Stack နှင့် တွဲဖက် အသုံးပြုဖို့ အကောင်းဆုံး အရာ ဖြစ်ပါတယ်။ ကွန်ပျူတာတွေဟာ သင်္ချာညီမျှခြင်းတွေကို တွက်ချက်တဲ့အခါ Stack ကို သုံးပြီး အခုလိုပဲ တွက်ချက်ပါတယ်။

အလွယ်ဆုံး စဥ်းစားနည်းကတော့ —

ဂဏန်း တွေ့ရင် Stack ထဲ ထည့် (Push)။
သင်္ကေတ (+, -, *, /) တွေ့ရင် Stack ထဲကနေ ဂဏန်း ၂ ခု ထုတ် (Pop) ပြီး တွက်ချက်ကာ ရလာတဲ့ အဖြေကို Stack ထဲ ပြန်ထည့် (Push) ပြုလုပ်သွားယုံပါပဲ။
နောက်ဆုံး Stack ထဲမှာ ကျန်နေတဲ့ ဂဏန်း ဟာ အဖြေ ဖြစ်ပါတယ်။

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            // Operator တွေ့ပါက တွက်ချက်ခြင်းပြုလုပ်သည်
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (token.equals("-")) {
                // အရင်ထွက်လာသည့်ဂဏန်းသည် အနောက်က ဂဏန်းဖြစ်သည်
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b - a);
            } else if (token.equals("/")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b / a);
            } else {
                // ဂဏန်းတွေ့ပါက Stack ထဲသို့ Integer ပြောင်း၍ ထည့်သည်
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
}

Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i^{th}$ day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

ဒီပုစ္ဆာမှာ နေ့စဉ် အပူချိန်တွေ ပေးထားပြီး နောက်ရက်တွေမှာ ကိုယ့်ထက် ပိုပူတဲ့နေ့ ရောက်ဖို့ ဘယ်နှရက် စောင့်ရမလဲ ဆိုတာကို ရှာရမှာပါ။

ရိုးရိုး Nested Loop နဲ့ ရှာရင် $O(n^2)$ ကြာပါမယ်။ Stack (Monotonic Decreasing Stack) ကို သုံးပြီး $O(n)$ နဲ့ ဖြေရှင်းလို့ ရပါတယ်။
Stack ထဲမှာ အပူချိန်ရဲ့ Index တွေကို သိမ်းပါမယ်။ လက်ရှိ ဝင်လာတဲ့ အပူချိန်က Stack ရဲ့ အပေါ်ဆုံးမှာ ရှိတဲ့ အပူချိန်ထက် ကြီးနေရင်၊ အဲ့ဒီ Stack ထဲက Index အတွက် ပိုပူတဲ့နေ့ကို တွေ့သွားပါပြီ။ ဒါကြောင့် Stack ကနေ Pop လုပ်ပြီး ရက်ကွာခြားချက် (Current Index - Popped Index) ကို အဖြေအဖြစ် မှတ်ယူပါမယ်။

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        // Index များကို သိမ်းမည့် Stack
        Stack<Integer> stack = new Stack<>(); 
        
        for (int i = 0; i < temperatures.length; i++) {
            // လက်ရှိ အပူချိန်သည် Stack အပေါ်ဆုံးမှ အပူချိန်ထက် ကြီးနေသရွေ့
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                // စောင့်ရမည့် ရက်အရေအတွက်ကို မှတ်သည်
                result[prevIndex] = i - prevIndex; 
            }
            stack.push(i);
        }
        
        return result;
    }
}

Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the $i^{th}$ car and speed[i] is the speed of the $i^{th}$ car in miles per hour.

A car cannot pass another car ahead of it. It can only catch up to another car and then drive at the same speed. A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
- The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.
- The car starting at 0 does not catch up to any other car, so it is a fleet by itself.
- The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6.
  The fleet moves at speed 1 until it reaches target.

ဒီပုစ္ဆာမှာ ကားတွေက ပန်းတိုင် (target) ကို သွားကြမှာပါ။ အနောက်ကကားက အမြန်မောင်းလို့ အရှေ့ကကားကို မီသွားရင်တောင် ကျော်တက်လို့ မရဘဲ အရှေ့ကားနဲ့ တစ်တန်းတည်း (Fleet) အဖြစ် ပတ်သက်သွားရမှာပါ။ နောက်ဆုံး ပန်းတိုင်ရောက်ရင် Fleet ဘယ်နှစု ဖြစ်မလဲဆိုတာ မေးတာပါ။

ဒီပုစ္ဆာကို ဖြေရှင်းဖို့ ကားတွေကို သူတို့ရဲ့ စတင်တဲ့ နေရာ (Position) အလိုက် အစဉ်လိုက် (အကြီးမှ အငယ်၊ ပန်းတိုင်နဲ့ အနီးဆုံးကနေ အဝေးဆုံး) စီ (Sort) စဉ်းစားပါမယ်။
ပြီးရင် ကားတစ်စီးစီ ပန်းတိုင်ရောက်ဖို့ ကြာမယ့် အချိန် (Distance / Speed) ကို တွက်ပါမယ်။
အနောက်ကလာတဲ့ ကားရဲ့ အချိန်ဟာ အရှေ့ကကားရဲ့ အချိန်ထက် ငယ်နေရင် (သို့) ညီနေရင် (ဆိုလိုတာက ပိုမြန်နေရင် သို့မဟုတ် တချိန်တည်းရောက်ရင်) အရှေ့ကားကို မီသွားပြီး Fleet တစ်ခုတည်း ဖြစ်သွားပါမယ်။ အချိန် ပိုကြီးနေရင်တော့ (ဆိုလိုတာက ပိုနှေးနေရင်) မမီတဲ့အတွက် Fleet အသစ် တစ်ခု ဖြစ်ပါမယ်။

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        // ကားများ၏ Position နှင့် ကြာမည့်အချိန်ကို တွဲသိမ်းရန် Array
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        
        // Position အလိုက် အငယ်မှ အကြီးစီသည်
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        
        Stack<Double> stack = new Stack<>();
        
        // ပန်းတိုင်နှင့် အနီးဆုံး ကား (Array ရဲ့ အနောက်ဆုံး) မှစ၍ ပြောင်းပြန် စစ်ဆေးသည်
        for (int i = n - 1; i >= 0; i--) {
            double time = cars[i][1];
            // Stack လွတ်နေလျှင် သို့မဟုတ် လက်ရှိကားသည် Stack ထဲရှိ အရှေ့ကားထက် အချိန်ပိုကြာလျှင် (နှေးပြီး မမီလျှင်)
            if (stack.isEmpty() || time > stack.peek()) {
                stack.push(time);
            }
            // အချိန်ပိုနည်းလျှင် (ပိုမြန်လျှင်) အရှေ့ကားကို မီသွား၍ Fleet တူသွားသဖြင့် Stack ထဲ ထပ်မထည့်ပါ
        }
        
        // Stack ၏ အရွယ်အစားသည် Fleet အရေအတွက် ဖြစ်သည်
        return stack.size();
    }
}

Largest Rectangle In Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is shown in the shaded area, which has an area = 10 units.

ဒီပုစ္ဆာကတော့ Histogram (တိုင်လေးတွေ) ထဲမှာ အကျယ်ဆုံး စတုဂံ ဧရိယာ ကို ရှာရမယ့် မေးခွန်းပါ။ Stack ကို သုံးပြီး $O(n)$ အချိန်နဲ့ တွက်ထုတ်နိုင်တဲ့ အကောင်းဆုံး အသုံးချမှုတစ်ခု ဖြစ်ပါတယ်။

Monotonic Increasing Stack ကို သုံးပါမယ်။ Stack ထဲမှာ တိုင်တွေရဲ့ index တွေကို အစဉ်လိုက် မြင့်လာသရွေ့ သိမ်းသွားပါမယ်။
လက်ရှိ တိုင်ရဲ့ အမြင့်က Stack ရဲ့ အပေါ်ဆုံးက တိုင်အမြင့်ထက် ငယ်သွားပြီ ဆိုရင်၊ Stack ထဲက အရှည်ဆုံး တိုင်တွေအတွက် နောက်ထပ် ဆန့်လို့ရမယ့် ဘက် (ညာဘက် နယ်နိမိတ်) ကို တွေ့သွားပါပြီ။
ဒါကြောင့် Stack ကနေ Pop လုပ်ပြီး၊ အမြင့် (height = heights[popped index]) နဲ့ အကျယ် (width = current_index - new_top_index - 1) ကို မြှောက်ကာ ဧရိယာ အကြီးဆုံးကို တွက်ချက် မှတ်သားသွားပါမယ်။

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i <= heights.length; i++) {
            // Array ပြီးဆုံးသွားလျှင် ကျန်နေသည့် Stack ကို ရှင်းရန် အမြင့် 0 ထည့်စဉ်းစားသည်
            int h = (i == heights.length) ? 0 : heights[i];
            
            // လက်ရှိအမြင့်သည် Stack အပေါ်ဆုံးမှ အမြင့်ထက် ငယ်နေသရွေ့ Pop လုပ်၍ ဧရိယာတွက်သည်
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                // Stack လွတ်သွားလျှင် အစကနေ လက်ရှိအထိ ကျယ်သည်ဟု ယူဆသည်
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}