증분 연산을 사용하여 스택 설계

1381. 증분 연산으로 스택 설계

난이도:중

주제: 어레이, 스택, 디자인

해당 요소에 대한 증분 연산을 지원하는 스택을 설계하세요.

CustomStack 클래스 구현:

• CustomStack(int maxSize) 스택의 최대 요소 수인 maxSize로 객체를 초기화합니다.
• void push(int x) 스택이 maxSize에 도달하지 않은 경우 스택 상단에 x를 추가합니다.
• int pop() 팝하고 스택의 맨 위를 반환하거나 스택이 비어 있으면 -1을 반환합니다.
• void inc(int k, int val) 스택의 아래쪽 k개 요소를 val만큼 증가시킵니다. 스택에 k개 미만의 요소가 있는 경우 스택의 모든 요소를 ​​증가시킵니다.

예 1:

• 입력:

  ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
  [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

• 출력:

  [null,null,null,2,null,null,null,null,null,103,202,201,-1]

• 설명:

   CustomStack stk = new CustomStack(3); // Stack is Empty []
   stk.push(1);                          // stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
   stk.push(2);                          // stack becomes [1, 2]
   stk.push(3);                          // stack becomes [1, 2, 3]
   stk.push(4);                          // stack still [1, 2, 3], Do not add another elements as size is 4
   stk.increment(5, 100);                // stack becomes [101, 102, 103]
   stk.increment(2, 100);                // stack becomes [201, 202, 103]
   stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
   stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes [201]
   stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes []
   stk.pop();                            // return -1 --> Stack is empty return -1.

제약조건:

• 1
• 0
• 각 증분, 푸시 및 팝 방법에 대해 각각 최대 1000번의 호출이 개별적으로 이루어집니다.

힌트:

1. 스택을 표현하려면 배열을 사용하세요. 푸시는 배열에 새로운 정수를 추가합니다. Pop은 배열의 마지막 요소를 제거하고 increment는 배열의 처음 k개 요소에 val을 추가합니다.
2. 이 솔루션은 푸시 및 팝당 O(1), 증분당 O(k)로 실행됩니다.

해결책:

일반적인 스택 구현을 따를 수 있지만 하위 k개 요소를 주어진 값만큼 증가시키는 추가 방법을 사용할 수 있습니다. 증분 작업은 스택의 처음 k개 요소를 반복하고 각 요소에 값을 추가합니다.

스택을 나타내는 배열을 사용하여 PHP 5.6에서 이 스택을 구현할 것입니다. 핵심 작업은 다음과 같습니다.

1. push(x): 스택이 최대 크기에 도달하지 않은 경우 x 요소를 스택 맨 위에 추가합니다.
2. pop(): 스택의 최상위 요소를 제거하고 반환합니다. 스택이 비어 있으면 -1을 반환합니다.
3. increment(k, val): 스택의 첫 번째 k개 요소에 val 값을 추가하거나, 스택에 k개 미만의 요소가 포함된 경우 모든 요소에 추가합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1381. 증분 연산으로 스택 설계

<?php class CustomStack {
    /**
     * @var array
     */
    private $stack;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * Constructor to initialize the stack with a given maxSize
     *
     * @param Integer $maxSize
     */
    function __construct($maxSize) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Push an element to the stack if it has not reached the maxSize
     *
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Pop the top element from the stack and return it, return -1 if the stack is empty
     *
     * @return Integer
     */
    function pop() {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }

    /**
     * Increment the bottom k elements of the stack by val
     *
     * @param Integer $k
     * @param Integer $val
     * @return NULL
     */
    function increment($k, $val) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * $obj = CustomStack($maxSize);
 * $obj->push($x);
 * $ret_2 = $obj->pop();
 * $obj->increment($k, $val);
 */

// Example usage
$customStack = new CustomStack(3);  // Stack is Empty []
$customStack->push(1);              // stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
echo $customStack->pop() . "\n";    // return 2, stack becomes [1]
$customStack->push(2);              // stack becomes [1, 2]
$customStack->push(3);              // stack becomes [1, 2, 3]
$customStack->push(4);              // stack still [1, 2, 3], maxSize is 3
$customStack->increment(5, 100);    // stack becomes [101, 102, 103]
$customStack->increment(2, 100);    // stack becomes [201, 202, 103]
echo $customStack->pop() . "\n";    // return 103, stack becomes [201, 202]
echo $customStack->pop() . "\n";    // return 202, stack becomes [201]
echo $customStack->pop() . "\n";    // return 201, stack becomes []
echo $customStack->pop() . "\n";    // return -1, stack is empty
?>

설명:

1. 푸시($x):

   • 스택에 요소를 추가하기 위해 array_push를 사용합니다. 스택의 현재 크기가 maxSize보다 작은지 확인합니다. 그렇다면 새 요소를 푸시합니다.

2. 팝():

   • empty($this->stack)을 사용하여 스택이 비어 있는지 확인합니다. 비어 있지 않으면 array_pop을 사용하여 최상위 요소를 팝하고 반환합니다. 비어 있으면 -1을 반환합니다.

3. 증분($k, $val):

   • k의 최소값과 현재 스택 크기를 계산하여 증가할 요소 수를 결정합니다. 그런 다음 각 요소에 val을 추가하여 이러한 요소를 반복합니다.

실행 예:

입력 작업의 경우:

["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]

출력은 다음과 같습니다.

[null, null, null, 2, null, null, null, null, null, 103, 202, 201, -1]

이 출력은 다음을 기반으로 합니다.

• push(1): 스택은 [1]이 됩니다.
• push(2): 스택은 [1, 2]가 됩니다.
• pop(): 2를 반환하고 스택은 [1]이 됩니다.
• push(2): 스택은 [1, 2]가 됩니다.
• push(3): 스택은 [1, 2, 3]이 됩니다.
• push(4): 스택은 [1, 2, 3]으로 유지됩니다(maxSize 도달)
• increment(5, 100): 스택은 [101, 102, 103]이 됩니다.
• increment(2, 100): 스택은 [201, 202, 103]이 됩니다.
• pop(): 103을 반환하고 스택은 [201, 202]가 됩니다.
• pop(): 202를 반환하고 스택은 [201]이 됩니다.
• pop(): 201을 반환하고 스택은 []가 됩니다.
• pop(): -1을 반환합니다(스택이 비어 있음)

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 증분 연산을 사용하여 스택 설계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!