monotonic stack

Algorithm/problem solving

leetcode 2104. Sum of Subarray Ranges

문제 요약 주어진 nums의 모든 subarray들의 (최대값 - 최소값) 들의 합을 구하는 문제였습니다. 이전의 풀어본 leetcode 907가 subarray의 최소값의 합이였기 때문에 이 문제를 기억하여 대략적으로 방향이 나올 수 있었습니다. 2023.05.01 - [Algorithm/problem solving] - leetcode 907. Sum of Subarray Minimums leetcode 907. Sum of Subarray Minimums 문제 요약 주어진 arr로 구성된 모든 subarray에서의 최소값들의 합을 구하는 문제였습니다. 해결 time limit exceed 접근법 처음에는 stack을 만들고 monotonic increasing stack을 만들고 매 index마다 ..

Algorithm/problem solving

leetcode 907. Sum of Subarray Minimums

문제 요약 주어진 arr로 구성된 모든 subarray에서의 최소값들의 합을 구하는 문제였습니다. 해결 time limit exceed 접근법 처음에는 stack을 만들고 monotonic increasing stack을 만들고 매 index마다 stack에 들어있는 것을 꺼내어 답을 도출했습니다. 하지만 매 index마다 stack에 들어있는 것을 꺼내는 과정이 사실 이 문제는 O(n)으로 끝내야 하는 문제인데 최악의 경우 O(n^2) 케이스가 발생될 수도 있어 time limit exceed가 발생되고 말았습니다. 수학적 접근법 따라서 이를 해결하기 위해선 수학적 접근법을 이용할 수 있는데요. 우선 특정 범위 내에서 최소값이 정해진다고 할 때 그 수 주변에 왼쪽, 오른쪽을 고려해볼 수 있습니다. 만약..

Brad Lee
'monotonic stack' 태그의 글 목록
상단으로

티스토리툴바