Stock Span Problem

Q: Độ phức tạp thời gian của bài toán khoảng thời gian cổ phiếu là bao nhiêu?

Độ phức tạp thời gian O(n) và bộ nhớ phụ O(n) khi dùng ngăn xếp đơn điệu, vì mỗi ngày chỉ rời khỏi ngăn xếp tối đa một lần. Duyệt ngược từ mỗi ngày có độ phức tạp O(n²) khi giá tiếp tục tăng hoặc giữ nguyên.

Q: Nên lưu giá hay chỉ số ngày trong ngăn xếp?

Chỉ số ngày. Khoảng thời gian là số ngày, và chỉ số của blocker mới cho bạn biết điều đó. prices[index] đọc lại giá để so sánh.

Q: Có thể giải bài toán khoảng giá cổ phiếu mà không cần dùng ngăn xếp riêng không?

Có. Bắt đầu từ j = today - 1 ; khi j ≥ 0 và prices[j] ≤ prices[today] , nhảy đến j - span[j] , vì giá của mỗi ngày trong khoảng đó không vượt quá prices[j] . Khoảng này là today - j . Các bước nhảy chỉ dừng ở những ngày mà ngăn xếp sẽ giữ lại, nên lượt duyệt vẫn có độ phức tạp O(n) .

Q: Bài toán khoảng thời gian giá cổ phiếu có phải là bài toán tìm phần tử lớn hơn trước đó không?

Đúng vậy, tính theo ngày: với mỗi ngày, bạn tìm ngày gần nhất trước đó có giá cao hơn hẳn và cho biết ngày đó cách bao xa. Đảo chiều quét hoặc đổi phép so sánh, cùng một ngăn xếp sẽ cho kết quả là ngày tiếp theo có giá cao hơn, ngày tiếp theo có giá thấp hơn hoặc ngày trước đó có giá thấp hơn.

Trung bìnhNgăn xếp đơn điệu

+10

Mỗi ngày, bạn nhận được giá đóng cửa của một cổ phiếu: prices[i] là giá vào ngày i. Khoảng thời gian của ngày i là số ngày liên tiếp, kết thúc vào ngày i và tính cả ngày đó, mà giá của những ngày này nhỏ hơn hoặc bằng prices[i].

Trả về khoảng thời gian của từng ngày, theo cùng thứ tự với prices. Mỗi khoảng thời gian ít nhất là 1, vì một ngày luôn tính cả chính nó.

Hàm

stockSpan(prices: integer-array) → integer-array

pricesinteger-array: giá vào từng ngày, theo thứ tự
Trả vềinteger-array: khoảng thời gian của mỗi ngày, theo cùng thứ tự

Ràng buộc

1 ≤ prices.length ≤ 10⁴
1 ≤ prices[i] ≤ 10⁵
Một ngày trước đó có cùng mức giá vẫn được tính vào khoảng thời gian này; chỉ mức giá cao hơn mới kết thúc khoảng thời gian đó.

Ví dụ

Đầu vào: prices = [31, 27, 14, 21, 30, 18, 40]
Đầu ra: [1, 1, 1, 2, 4, 1, 7]
Giải thích: Ngày 3 ở mức 21 nhìn lại 14 ngày trước và dừng ở ngày 27: khoảng cách 2. Ngày 4 ở mức 30 dừng ở ngày 31: khoảng cách 4. Ngày 6 ở mức 40 cao hơn mọi mức giá trước đó và bao quát cả 7 ngày.

Câu hỏi mở rộng

Giờ đây, giá được gửi đến lần lượt từng giá một, và bạn phải báo cáo từng khoảng ngay khi nhận được giá. Cách tiếp cận nào vẫn hoạt động, và nó giữ lại điều gì giữa các lần gọi?

Lời giải

Khoảng thời gian của một ngày kết thúc ở ngày gần nhất trước đó có giá cao hơn nghiêm ngặt. Đi ngược lại để tìm ngày đó có thể tốn đến n bước cho mỗi ngày. Thay vào đó, chỉ giữ lại những ngày vẫn có thể chặn khoảng thời gian trong tương lai: một ngăn xếp chỉ số có giá giảm nghiêm ngặt sẽ tìm được mọi ranh giới chỉ trong một lượt.

Đếm ngược từ mỗi ngày

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Làm theo định nghĩa. Với ngày i, lùi từng ngày một khi giá ở ngày đó nhỏ hơn hoặc bằng prices[i], tính cả ngày i. Giá đầu tiên cao hơn hẳn, hoặc đầu mảng, sẽ kết thúc lượt lùi.

Mỗi lần duyệt không dùng lại kết quả của lần trước. Khi giá đi ngang hoặc tăng, mỗi lần duyệt đều lùi về ngày 0: n = 10^4 ngày tương đương khoảng 5 × 10^7 bước.

Thuật toán

Tạo span, một mảng có độ dài bằng prices.
Với mỗi ngày i, đặt bộ đếm về 0 và con trỏ j bằng i.
Trong khi j ≥ 0 và prices[j] ≤ prices[i], tăng bộ đếm thêm 1 và lùi j lại một ngày.
Lưu bộ đếm vào span[i]. Sau ngày cuối cùng, trả về span.

def stockSpan(prices):
    span = []
    for i in range(len(prices)):
        count = 0
        j = i
        # Count today and every earlier day in a row that is not more expensive.
        while j >= 0 and prices[j] <= prices[i]:
            count += 1
            j -= 1
        span.append(count)
    return span

Ngăn xếp đơn điệu gồm các ngày có nhiệt độ cao hơn

Ý tưởng

Gọi ngày gần nhất trước hôm nay có giá cao hơn nghiêm ngặt là ngày chặn. Khoảng thời gian là today - blocker, hoặc today + 1 nếu không có ngày nào như vậy.

Trong ví dụ đầu tiên, ngày 3 có giá 21 và ngày 4 có giá 30. Mọi lần duyệt về sau đều gặp ngày 4 trước, và bất kỳ mức giá nào vượt qua 30 cũng vượt qua 21, vì vậy ngày 3 không thể chặn thêm lần nào nữa. Nói chung, khi hôm nay đến, mọi ứng viên trước đó có giá nhỏ hơn hoặc bằng giá hôm nay đều không còn cần thiết: hãy lấy chúng ra. Ngày còn lại trên đỉnh chính là ngày chặn hôm nay. Sau đó, thêm hôm nay vào.

Giá trên ngăn xếp giảm nghiêm ngặt từ dưới lên trên, vì vậy phần tử đầu tiên còn lại là mức giá cao hơn gần nhất. Trong ví dụ đầu tiên, ngày 4 lấy các ngày 3 và 1 ra rồi dừng ở ngày 0, tạo thành khoảng thời gian 4 - 0 = 4. Mỗi ngày được thêm vào một lần và lấy ra nhiều nhất một lần, nên lượt duyệt chạy trong O(n).

Thuật toán

Tạo mảng span và một ngăn xếp rỗng để lưu các chỉ số ngày.
Với mỗi ngày today, lấy các chỉ số ra khỏi ngăn xếp khi giá của chúng nhỏ hơn hoặc bằng prices[today].
Nếu ngăn xếp rỗng, khoảng thời gian là today + 1; nếu không, khoảng thời gian bằng today trừ đi chỉ số ở trên cùng.
Đẩy today vào ngăn xếp rồi chuyển sang ngày tiếp theo. Trả về span.

def stockSpan(prices):
    span = [0] * len(prices)
    higher = []  # indices of earlier days, prices strictly falling toward the top
    for today, price in enumerate(prices):
        # A day that is not more expensive than today can never stop a later span.
        while higher and prices[higher[-1]] <= price:
            higher.pop()
        # The span reaches back to the nearest more expensive day, or to day 0.
        span[today] = today - higher[-1] if higher else today + 1
        higher.append(today)
    return span

Lỗi thường gặp và trường hợp biên

Lấy phần tử ra khi gặp < thay vì <=. Trong [8, 8, 3, 8], ngày cuối cùng có khoảng thời gian là 4; dừng ở số 8 trước đó thì kết quả là 2.
Ghi today thay vì today + 1 khi ngăn xếp trống. Ngày 0 phải nhận giá trị 1, không phải 0.
Chỉ lấy một phần tử ra mỗi ngày. Trong ví dụ đầu tiên, 40 phải vượt qua các ngày 5, 4 và 0. Nếu dừng sau ngày 5, ngày 4 trông như phần tử cản trở, khiến khoảng thời gian là 2 thay vì 7.
Trong Lua và R, mảng bắt đầu từ 1. Với chỉ số bắt đầu từ 1, khoảng thời gian khi ngăn xếp trống là today, không phải today + 1.

Câu hỏi thường gặp4

Độ phức tạp thời gian của bài toán khoảng thời gian cổ phiếu là bao nhiêu?

Độ phức tạp thời gian O(n) và bộ nhớ phụ O(n) khi dùng ngăn xếp đơn điệu, vì mỗi ngày chỉ rời khỏi ngăn xếp tối đa một lần. Duyệt ngược từ mỗi ngày có độ phức tạp O(n²) khi giá tiếp tục tăng hoặc giữ nguyên.

Nên lưu giá hay chỉ số ngày trong ngăn xếp?

Chỉ số ngày. Khoảng thời gian là số ngày, và chỉ số của blocker mới cho bạn biết điều đó. prices[index] đọc lại giá để so sánh.

Có thể giải bài toán khoảng giá cổ phiếu mà không cần dùng ngăn xếp riêng không?

Có. Bắt đầu từ j = today - 1; khi j ≥ 0 và prices[j] ≤ prices[today], nhảy đến j - span[j], vì giá của mỗi ngày trong khoảng đó không vượt quá prices[j]. Khoảng này là today - j. Các bước nhảy chỉ dừng ở những ngày mà ngăn xếp sẽ giữ lại, nên lượt duyệt vẫn có độ phức tạp O(n).

Bài toán khoảng thời gian giá cổ phiếu có phải là bài toán tìm phần tử lớn hơn trước đó không?

Đúng vậy, tính theo ngày: với mỗi ngày, bạn tìm ngày gần nhất trước đó có giá cao hơn hẳn và cho biết ngày đó cách bao xa. Đảo chiều quét hoặc đổi phép so sánh, cùng một ngăn xếp sẽ cho kết quả là ngày tiếp theo có giá cao hơn, ngày tiếp theo có giá thấp hơn hoặc ngày trước đó có giá thấp hơn.

def stockSpan(prices):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

prices = [31, 27, 14, 21, 30, 18, 40]

Đầu ra mong đợi

[1, 1, 1, 2, 4, 1, 7]