รูปแบบสแตกโมโนโทน
ใช้สแตกโมโนโทนแก้โจทย์อุณหภูมิรายวัน สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม และองค์ประกอบที่มากกว่าถัดไปในเวลา O(n)
รูปแบบสแตกโมโนโทน เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
สแตกโมโนโทนิกคืออะไร
สแตกโมโนโทนิก คือสแตกที่รักษาเงื่อนไขคงตัวของการเรียงลำดับระหว่างสมาชิกไว้ สแตกโมโนโทนิกแบบเพิ่มขึ้น มีสมาชิกเรียงจากน้อยไปมากเมื่อดูจากล่างขึ้นบน ส่วน สแตกโมโนโทนิกแบบลดลง มีสมาชิกเรียงจากมากไปน้อยเมื่อดูจากล่างขึ้นบน เมื่อสมาชิกใหม่ละเมิดเงื่อนไขคงตัว สมาชิกจะถูกนำออกจนกว่าเงื่อนไขจะกลับมาเป็นจริง จากนั้นจึงเพิ่มสมาชิกใหม่เข้าไป
กลไกที่เรียบง่ายนี้ทำให้ตอบคำถามเกี่ยวกับ 'สมาชิกที่มากกว่าหรือเล็กกว่าที่ใกล้ที่สุด' ได้ด้วยความซับซ้อน O(n) ทั้งที่วิธีตรงไปตรงมาอาจต้องใช้ลูปซ้อนกันด้วยความซับซ้อน O(n²)
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)สมาชิกที่มากกว่าถัดไป (LeetCode 496)
สำหรับสมาชิกแต่ละตัว ให้ค้นหาสมาชิกตัวแรกทางขวาที่มีค่ามากกว่าอย่างเคร่งครัด วิธีตรวจสอบแบบตรงไปตรงมาด้วยความซับซ้อน O(n²) จะไล่ค้นไปทางขวาจากแต่ละตำแหน่ง ส่วนวิธีใช้สแตกโมโนโทนิกจะรักษาสแตกแบบลดลงของ ดัชนี เมื่อพบสมาชิกที่มีค่ามากกว่า ให้ นำดัชนีของสมาชิกที่เล็กกว่าทั้งหมดออก เพราะสมาชิกปัจจุบันคือ 'สมาชิกที่มากกว่าถัดไป' ของสมาชิกเหล่านั้น ดัชนีที่เหลือไม่มีสมาชิกที่มากกว่าถัดไป คำตอบจึงเป็น -1
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]สมาชิกที่มากกว่าถัดไปในอาร์เรย์วงกลม
LeetCode 503 'สมาชิกที่มากกว่าถัดไป II': เป็นปัญหาเดียวกัน แต่อาร์เรย์จะถือว่าเป็นวงกลม เมื่อไปถึงจุดสิ้นสุดแล้ว ให้ย้อนกลับไปตรวจสอบต่อจากจุดเริ่มต้น เคล็ดลับคือวนผ่านอาร์เรย์สองรอบ (ดัชนี 0 ถึง 2n-1) และใช้ i % n เพื่ออ้างอิงตำแหน่งในอาร์เรย์เดิม ให้เพิ่มเฉพาะดัชนีในช่วง [0, n-1] เพื่อหลีกเลี่ยงการประมวลผลซ้ำ
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]อุณหภูมิรายวัน: วิธีแก้โจทย์ฉบับสมบูรณ์
ทบทวน LeetCode 739: สำหรับแต่ละวัน ต้องรอกี่วันจึงจะพบอุณหภูมิที่สูงกว่า สแตกโมโนโทนิกจะเก็บดัชนีของวันที่มีอุณหภูมิเรียงใน ลำดับลดลง เมื่อพบวันที่ i ซึ่งอุ่นกว่า ให้นำดัชนี j ของวันที่เย็นกว่าทั้งหมดออกจากสแตก แล้วบันทึก result[j] = i - j วันที่ยังเหลืออยู่ในสแตกไม่เคยพบวันที่อุ่นกว่า ดังนั้นผลลัพธ์ของวันเหล่านั้นจึงยังคงเป็น 0
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]สมาชิกที่เล็กกว่าก่อนหน้า
คำถามเกี่ยวกับ 'สมาชิกที่เล็กกว่าก่อนหน้า' ถามว่า สำหรับสมาชิกแต่ละตัว ค่าที่เล็กกว่าซึ่งอยู่ใกล้ที่สุดทางซ้ายคือค่าใด ให้ใช้สแตกโมโนโทนิกแบบเพิ่มขึ้นและประมวลผลจากซ้ายไปขวา ก่อนเพิ่มดัชนี i สมาชิกที่อยู่บนสุดของสแตกคือสมาชิกที่เล็กกว่าก่อนหน้า เพราะสมาชิกทั้งหมดที่มีค่ามากกว่าค่าที่ตำแหน่ง i ในอาร์เรย์ถูกนำออกไปแล้วระหว่างการเพิ่มสมาชิกก่อนหน้า ซึ่งทำให้สมาชิกที่มีค่ามากกว่าถูกนำออก
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม
LeetCode 84 'สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม': ใช้สแตกแบบ เพิ่มขึ้นของดัชนี สำหรับแท่งแต่ละแท่ง ให้นำแท่งทั้งหมดที่สูงกว่าแท่งปัจจุบันออก สำหรับแท่งที่ถูกนำออกแต่ละแท่ง h ขอบเขตด้านขวาคือดัชนีปัจจุบัน i ส่วนขอบเขตด้านซ้ายคือสมาชิกบนสุดตัวใหม่ของสแตก + 1 (หรือ 0 หากสแตกว่าง) พื้นที่ = h × (ขอบเขตขวา - ขอบเขตซ้าย) เพิ่มค่าตัวแทนที่มีความสูง 0 ต่อท้ายเพื่อบังคับให้นำแท่งที่เหลือทั้งหมดออกเมื่อสิ้นสุด
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1สี่เหลี่ยมผืนผ้าขนาดใหญ่ที่สุด (LeetCode 85)
LeetCode 85 'สี่เหลี่ยมผืนผ้าขนาดใหญ่ที่สุด' ขยายปัญหาฮิสโตแกรมไปเป็นเมทริกซ์ไบนารีสองมิติ สำหรับแต่ละแถว ให้คำนวณความสูงสะสมของแท่ง: หาก matrix[row][col] == '1' ความสูงคือจำนวนเลข 1 ที่ต่อเนื่องกันด้านบนและรวมเซลล์นี้ด้วย จากนั้นใช้อัลกอริทึม 'สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม' กับอาร์เรย์ความสูงของแต่ละแถว เวลา: O(m × n) สำหรับเมทริกซ์ขนาด m×n
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6การกักเก็บน้ำฝน: วิธีใช้สแตก
LeetCode 42 'การกักเก็บน้ำฝน' ด้วยสแตก: รักษาสแตกแบบลดลงของดัชนี เมื่อพบแท่งที่สูงกว่า จะเกิดแอ่งน้ำ ให้นำก้นแอ่งออก แล้วคำนวณความกว้างของน้ำเป็น (ดัชนีปัจจุบัน - ดัชนีบนสุดของสแตก - 1) และความสูงเป็น (ค่าต่ำสุดระหว่างแท่งปัจจุบันกับแท่งบนสุดตัวใหม่ของสแตก - ความสูงของก้นแอ่ง) จากนั้นรวมปริมาณน้ำทั้งหมด เวลา: O(n), พื้นที่หน่วยความจำ: O(n)
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9การสังเกตปัญหาที่เหมาะกับสแตกโมโนโทนิก
สัญญาณที่บ่งบอกว่าสแตกโมโนโทนิกเป็นเครื่องมือที่เหมาะสม ได้แก่ โจทย์ถามหา สมาชิกที่มากกว่าหรือเล็กกว่าถัดไปหรือก่อนหน้า คำตอบของสมาชิกแต่ละตัวขึ้นอยู่กับสมาชิกในทิศทางใดทิศทางหนึ่ง หรือวิธีแก้แบบตรงไปตรงมาด้วยความซับซ้อน O(n²) ต้องไล่ค้นไปทางซ้ายหรือขวาสำหรับสมาชิกแต่ละตัว สแตกจะเก็บสมาชิกที่อาจเป็นคำตอบของสมาชิกในอนาคต และทิ้งสมาชิกเหล่านั้นทันทีที่มีสมาชิกที่ดีกว่าเข้ามา
ควรตัดสินใจตั้งแต่ต้นเสมอว่าจะใช้สแตกแบบเพิ่มขึ้น (สำหรับสมาชิกที่เล็กกว่าถัดไปหรือก่อนหน้า) หรือแบบลดลง (สำหรับสมาชิกที่มากกว่าถัดไปหรือก่อนหน้า) และจะประมวลผลจากทิศทางใด
การวิเคราะห์ความซับซ้อน O(n) แบบเฉลี่ยตัดจำหน่าย
ในตอนแรก อัลกอริทึมสแตกโมโนโทนิกอาจดูเหมือนมีความซับซ้อน O(n log n) หรือ O(n²) เพราะมีลูป while อยู่ภายในลูป for แต่สมาชิกแต่ละตัวจะถูก เพิ่มเข้าไปอย่างมากหนึ่งครั้งและนำออกอย่างมากหนึ่งครั้ง จำนวนการเพิ่มทั้งหมดเท่ากับ n และจำนวนการนำออกทั้งหมดก็ไม่เกิน n เช่นกัน ดังนั้นเมื่อพิจารณาทุกรอบ งานทั้งหมดคือการดำเนินการ 2n ครั้ง หรือมีความซับซ้อน O(n) แบบเฉลี่ยตัดจำหน่าย ไม่ใช่ O(n²)
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nสรุป: การเลือกเงื่อนไขคงตัวของสแตกโมโนโทนิก
เลือกทิศทางของสแตกตามคำถาม สำหรับ สมาชิกที่มากกว่าถัดไป ให้ใช้ สแตกแบบลดลง โดยนำสมาชิกออกเมื่อสมาชิกปัจจุบันมีค่ามากกว่า สำหรับ สมาชิกที่เล็กกว่าถัดไป ให้ใช้ สแตกแบบเพิ่มขึ้น โดยนำสมาชิกออกเมื่อสมาชิกปัจจุบันมีค่าน้อยกว่า สำหรับ สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุด ให้ใช้สแตกแบบเพิ่มขึ้นและนำสมาชิกออกเมื่อพบแท่งที่เตี้ยกว่า สำหรับ ค่าสูงสุดในหน้าต่างเลื่อน ให้ใช้คิวสองปลายแบบลดลงและนำสมาชิกออกจากทั้งสองด้าน
การเขียนเงื่อนไขคงตัวไว้ในความคิดเห็นก่อนเริ่มเขียนโค้ดจะช่วยให้ตรรกะชัดเจนและแก้ไขข้อผิดพลาดได้เร็วขึ้น
ตรวจสอบอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า สแตกโมโนโทนิกจะรักษาเงื่อนไขคงตัวของการเรียงลำดับด้วยการนำสมาชิกที่ละเมิดเงื่อนไขออกก่อนเพิ่มสมาชิกใหม่ สแตกแบบลดลงใช้ตอบคำถามเกี่ยวกับสมาชิกที่มากกว่าถัดไป ส่วนสแตกแบบเพิ่มขึ้นใช้ตอบคำถามเกี่ยวกับสมาชิกที่เล็กกว่าถัดไป และ เวลารวมมีความซับซ้อน O(n) แบบเฉลี่ยตัดจำหน่าย เพราะสมาชิกแต่ละตัวถูกเพิ่มและนำออกอย่างมากหนึ่งครั้ง ต่อไปเราจะสร้างคิวโดยใช้สแตก และสร้างสแตกโดยใช้คิว
คำถามที่พบบ่อย
บทเรียน “รูปแบบสแตกโมโนโทน” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “รูปแบบสแตกโมโนโทน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “รูปแบบสแตกโมโนโทน”
ใช้สแตกโมโนโทนแก้โจทย์อุณหภูมิรายวัน สี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดในฮิสโตแกรม และองค์ประกอบที่มากกว่าถัดไปในเวลา O(n) คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “รูปแบบสแตกโมโนโทน” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ