สแตกโมโนโทนิก: เพิ่มขึ้นเทียบกับลดลง

สแตกแบบเพิ่มหรือลดอย่างเดียวคืออะไร

# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
    while stack and stack[-1] > val:
        stack.pop()          # maintain increasing invariant
    stack.append(val)
print('Increasing stack (left-to-right):', stack)  # [1, 1, 2, 6]

# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
    while stack and stack[-1] < val:
        stack.pop()          # maintain decreasing invariant
    stack.append(val)
print('Decreasing stack (left-to-right):', stack)  # [9, 6]

สมาชิกที่มากกว่าถัดไป I

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []   # stores indices; stack values are decreasing

    for i in range(n):
        # Pop elements smaller than nums[i]
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]   # nums[i] is next greater for idx
        stack.append(i)
    # Remaining elements in stack have no next greater => keep -1
    return result

nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums))  # [4, 2, 4, -1, -1]

nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]

สมาชิกถัดไปที่มีค่ามากกว่า: การติดตามอัลกอริทึม

def next_greater_trace(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(n):
        print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
            print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
        stack.append(i)
        print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
    print('Result:', result)
    return result

next_greater_trace([2, 1, 2, 4, 3])

สมาชิกก่อนหน้าที่มีค่าน้อยกว่า

def previous_smaller_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []   # monotonic increasing (values increase bottom to top)

    for i in range(n):
        # Pop elements >= current (maintain strictly increasing invariant)
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        # Top of stack is previous smaller element (if exists)
        if stack:
            result[i] = nums[stack[-1]]
        stack.append(i)
    return result

nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums))  # [-1, 4, -1, 2, 2]

nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]

อุณหภูมิรายวัน: รอวันที่อุ่นขึ้น

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []   # indices of unresolved days

    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            j = stack.pop()
            result[j] = i - j   # days until warmer
        stack.append(i)
    return result

temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0]  (always warmer next day)

temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]

สแตกแบบเพิ่มขึ้นเทียบกับแบบลดลง: ควรใช้เมื่อใด

# Summary: which stack type for which query?
queries = {
    'Next Greater Element':    'Decreasing stack (pop when new > top)',
    'Next Smaller Element':    'Increasing stack (pop when new < top)',
    'Previous Greater Element': 'Decreasing stack (answer = top before push)',
    'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
    print(f'{query}:\n  => {approach}\n')

# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)

สมาชิกถัดไปที่มีค่ามากกว่าในอาร์เรย์วงกลม

def next_greater_element_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            idx = stack.pop()
            result[idx] = nums[i % n]
        if i < n:
            stack.append(i)   # only push real indices (0..n-1)
    return result

print(next_greater_element_circular([1, 2, 1]))    # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3]))  # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1]))  # [-1, 5, 5, 5, 5]

ปัญหาช่วงราคาหุ้น

def stock_span(prices):
    spans = []
    stack = []   # indices of prices forming decreasing sequence

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        span = i - stack[-1] if stack else i + 1
        spans.append(span)
        stack.append(i)
    return spans

prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices))  # [1, 1, 1, 2, 1, 4, 6]

# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6

สแตกแบบโมโนโทนิกสำหรับบุคคลที่มองเห็นได้ในแถว

def visible_people(heights):
    n = len(heights)
    result = [0] * n
    stack = []   # decreasing monotonic stack (heights)

    for i in range(n - 1, -1, -1):   # right to left
        count = 0
        while stack and stack[-1] < heights[i]:
            stack.pop()
            count += 1   # can see this shorter person
        if stack:
            count += 1   # can see the first person >= heights[i]
        result[i] = count
        stack.append(heights[i])
    return result

heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights))  # [3, 1, 2, 1, 1, 0]

การรับประกัน O(n): เหตุใดสมาชิกทุกตัวจึงถูกใส่และนำออกจากสแตกไม่เกินหนึ่งครั้ง

def next_greater_instrumented(nums):
    result = [-1] * len(nums)
    stack = []
    pushes = pops = 0

    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
            pops += 1
        stack.append(i)
        pushes += 1

    print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
    print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
    return result

import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2n

การสังเกตปัญหาที่ใช้สแตกแบบโมโนโทนิก

# Monotonic stack problem recognition guide
patterns = [
    ('Next/previous greater element', 'Decreasing stack; answer found on pop'),
    ('Next/previous smaller element', 'Increasing stack; answer found on pop'),
    ('Days until warmer/colder',       'Stack of indices; answer = i - j'),
    ('Stock span',                     'Decreasing stack; span = i - prev larger idx'),
    ('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
    ('Trapping rain water',            'Decreasing stack or two-pointer'),
    ('Sliding window maximum',         'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
    print(f'Problem: {problem}')
    print(f'  Approach: {approach}')
    print()

ตรวจสอบความเข้าใจ

สรุปบทเรียน